Problem:


Score : 600 points

Problem Statement

Kenkoooo found a simple connected graph.
The vertices are numbered 1 through n.
The i-th edge connects Vertex u_i and v_i, and has a fixed integer s_i.

Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:

For every edge i, the sum of the positive integers written in Vertex u_i and v_i is equal to s_i.

Find the number of such ways to write positive integers in the vertices.

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq u_i < v_i \leq n

2 \leq s_i \leq 10^9

If i\neq j, then u_i \neq u_j  or v_i \neq v_j.

The graph is connected.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

n m
u_1 v_1 s_1
:
u_m v_m s_m

Output

Print the number of ways to write positive integers in the vertices so that the condition is satisfied.

Sample Input 1

3 3
1 2 3
2 3 5
1 3 4

Sample Output 1

1

The condition will be satisfied if we write 1,2 and 3 in vertices 1,2 and 3, respectively.
There is no other way to satisfy the condition, so the answer is 1.

Sample Input 2

4 3
1 2 6
2 3 7
3 4 5

Sample Output 2

3

Let a,b,c and d be the numbers to write in vertices 1,2,3 and 4, respectively.
There are three quadruples (a,b,c,d) that satisfy the condition:

(a,b,c,d)=(1,5,2,3)

(a,b,c,d)=(2,4,3,2)

(a,b,c,d)=(3,3,4,1)

Sample Input 3

8 7
1 2 1000000000
2 3 2
3 4 1000000000
4 5 2
5 6 1000000000
6 7 2
7 8 1000000000

Sample Output 3

0



Sample input:
3 3
1 2 3
2 3 5
1 3 4


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def is_bipartite(graph):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False
    return True


def color_bipartite(graph):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    return col
             

def make_spanning_tree(graph, root):
    """与えられたグラフから全域木をつくり、二部グラフとして彩色する"""
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    """木のsからtへのパスの頂点を出力する"""
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a, b = a - 1, b - 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

if is_bipartite(graph):
    col = color_bipartite(graph)
    ans = [-1] * n
    ans[0] = 1
    q = deque([0])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, ans[i])
        else:
            min_b = min(min_b, ans[i])
    if min_w < 1:
        min_b += -1 + min_w
        min_w -= -1 + min_w
    print(max(min_b, 0))
    
else:
    col, tree = make_spanning_tree(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
    if res % 2 == 1:
        print(0)
        exit()
    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [-1] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
            else:
                if ans[nxt_v] == cost - ans[v]:
                    continue
                else:
                    print(0)
                    exit()
    if min(ans) >= 1:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def is_bipartite(graph):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False
    return True


def color_bipartite(graph):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    return col
             

def make_bipartite(graph, root):
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a, b = a - 1, b - 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

if is_bipartite(graph):
    col = color_bipartite(graph)
    ans = [-1] * n
    ans[0] = 1
    q = deque([0])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, ans[i])
        else:
            min_b = min(min_b, ans[i])
    if min_w < 1:
        min_b += -1 + min_w
        min_w -= -1 + min_w
    print(max(min_b, 0))
    
else:
    col, tree = make_bipartite(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [-1] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
            else:
                if ans[nxt_v] == cost - ans[v]:
                    continue
                else:
                    print(0)
                    exit()
    print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def is_bipartite(graph):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False
    return True


def color_bipartite(graph):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    return col
             

def make_bipartite(graph, root):
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a, b = a - 1, b - 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

if is_bipartite(graph):
    print(-1)
    col = color_bipartite(graph)
    val = [-1] * n
    q = deque([0])
    val[0] = 1
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if val[nxt_v] == -1:
                val[nxt_v] = cost - val[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, val[i])
        else:
            min_b = min(min_b, val[i])
    if min_w < 1:
        min_b += 1 + min_w
        min_w = 1
    print(max(min_b, 0))
    
else:
    col, tree = make_bipartite(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [-1] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
            else:
                if ans[nxt_v] == cost - ans[v]:
                    continue
                else:
                    print(0)
                    exit()
    print(1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque


def is_bipartite(graph):
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False, col
    return True, col
             

def make_bipartite(graph, root):
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

boolian, col = is_bipartite(graph)
if boolian:
    val = [-1] * n
    q = deque([0])
    val[0] = 1
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if val[nxt_v] == -1:
                val[nxt_v] = cost - val[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, val[i])
        else:
            min_b = min(min_b, val[i])
    if min_w < 1:
        min_b += 1 + min_w
        min_w = 1
    print(max(min_b, 0))
    
else:
    col, tree = make_bipartite(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [-1] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
            else:
                if ans[nxt_v] == cost - ans[v]:
                    continue
                else:
                    print(0)
                    exit()
    print(1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
UVS = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for u,v,s in UVS:
    u,v = u-1,v-1
    es[u].append((v,s))
    es[v].append((u,s))

vs = [None] * N
cs = [None] * N
vs[0] = cs[0] = 0
stack = [0]
nibu = True
tmp0 = None
while stack:
    v = stack.pop()
    for to,s in es[v]:
        if vs[to] is None:
            vs[to] = s - vs[v]
            cs[to] = 1 - cs[v]
            stack.append(to)
        else:
            if cs[v] != cs[to]:
                if vs[v] + vs[to] == s: continue
                print(0)
                exit()
            nibu = False
            vv = vs[v] + vs[to]
            if s%2  != vv%2:
                print(0)
                exit()
            tmp = (vv-s)//2
            if tmp0 is None:
                tmp0 = tmp
            elif tmp0 != tmp:
                print(0)
                exit()

INF = float('inf')
emin = omin = INF
for v,c in zip(vs,cs):
    if c:
        omin = min(omin, v)
    else:
        emin = min(emin, v)
if nibu:
    if omin <= 0:
        emin -= (1-omin)
        omin = 1
    if emin <= 0:
        omin -= (1-emin)
        emin = 1
    if omin <= 0:
        print(0)
    else:
        print(abs(emin - omin) + 1)
else:
    emin += tmp0
    omin -= tmp0
    print(1 if emin > 0 and omin > 0 else 0)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v, s = map(int, input().split())
  e[u].append((v, s))
  e[v].append((u, s))

def check(x):
  a = [0] * (N + 1)
  a[1] = x
  s = [1]
  while len(s):
    p = s.pop()
    for q in e[p]:
      y, c = q
      if a[y]:
        if a[y] != c - a[p]: return False
        continue
      if c - a[p] <= 0: return False
      a[y] = c - a[p]
      s.append(y)
  return True

if check(1):
  ok = 1
  ng = 10 ** 9
  while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m): ok = m
    else: ng = m
  print(ok)
else:
  k = float("inf")
  for x in e[1]: k = min(k, x[1])
  ok = k
  ng = 1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if check(m): ok = m
    else: ng = m
  print(k - ok)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())

E=[[] for i in range(n+1)]

for i in range(m):
    x,y,s=map(int,input().split())
    E[x].append((y,s))
    E[y].append((x,s))

Q=[1]
USE=[-1]*(n+1)
USE[1]=0
FROM=[-1]*(n+1)

flag=1
while Q and flag==1:
    x=Q.pop()
    for to,c in E[x]:
        if USE[to]==USE[x]:
            flag=0
            flagpoint=to
            break
        if USE[to]==-1:
            Q.append(to)
            USE[to]=1-USE[x]
            FROM[to]=x

if flag==0:
    Q=[flagpoint]
    FROM=[-1]*(n+1)
    FROM[flagpoint]=-5
    USE=[-1]*(n+1)
    USE[flagpoint]=0
    flag=1
    while Q and flag==1:
        x=Q.pop()

        for to,c in E[x]:
            if USE[to]==USE[x]:
                flag=0
                break

            if FROM[to]==-1:
                Q.append(to)
                FROM[to]=x
                USE[to]=1-USE[x]

    S1=[to,x]
    while S1[-1]!=flagpoint:
        S1.append((FROM[S1[-1]]))

    S2=[to]
    while S2[-1]!=flagpoint:
        S2.append((FROM[S2[-1]]))

    #print(S1,S2)

    ROOP=S1+S2[1:-1]
    #print(ROOP)

    score=0
    ind=0

    NOW=flagpoint
    for ind in range(len(ROOP)):
        for to,c in E[ROOP[ind-1]]:
            if to==ROOP[ind]:
                score+=c*(-1)**(ind%2)
                break
        #print(score)
    #print(score)

    if score%2!=0 or score<=0:
        print(0)
        sys.exit()

    ANS=[-1]*(n+1)
        
    ANS[flagpoint]=score//2

    Q=[flagpoint]
    USE=[0]*(n+1)

    while Q:
        x=Q.pop()
        for to,c in E[x]:
            if USE[to]==0:
                USE[to]=1
                ANS[to]=c-ANS[x]
                Q.append(to)

    for i in range(1,n+1):
        if ANS[i]<=0:
            print(0)
            sys.exit()

    flag=1
    for i in range(n+1):
        for to,c in E[i]:
            if ANS[to]+ANS[i]!=c:
                flag=0
                print(0)
                sys.exit()

    print(1)
    sys.exit()

Q=[1]
score=[-1<<31]*(n+1)
score[1]=0
while Q:
    x=Q.pop()
    for to,c in E[x]:
        if score[to]==-1<<31:
            score[to]=c-score[x]
            Q.append(to)
        else:
            if score[to]!=c-score[x]:
                print(0)
                sys.exit()

MIN0=0
MIN1=1<<31

for i in range(1,n+1):
    if USE[i]==0:
        MIN0=min(MIN0,score[i])
    else:
        MIN1=min(MIN1,score[i])

#print(MIN0,MIN1)
print(max(0,max(0,MIN1)+MIN0-1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())

E=[[] for i in range(n+1)]

for i in range(m):
    x,y,s=map(int,input().split())
    E[x].append((y,s))
    E[y].append((x,s))

Q=[1]
USE=[-1]*(n+1)
USE[1]=0
FROM=[-1]*(n+1)

flag=1
while Q and flag==1:
    x=Q.pop()
    for to,c in E[x]:
        if USE[to]==USE[x]:
            flag=0
            flagpoint=to
            break
        if USE[to]==-1:
            Q.append(to)
            USE[to]=1-USE[x]
            FROM[to]=x

if flag==0:
    Q=[flagpoint]
    FROM=[-1]*(n+1)
    FROM[flagpoint]=-5
    USE=[-1]*(n+1)
    USE[flagpoint]=0
    flag=1
    while Q and flag==1:
        x=Q.pop()

        for to,c in E[x]:
            if USE[to]==USE[x]:
                flag=0
                break

            if FROM[to]==-1:
                Q.append(to)
                FROM[to]=x
                USE[to]=1-USE[x]

    S1=[to,x]
    while S1[-1]!=flagpoint:
        S1.append((FROM[S1[-1]]))

    S2=[to]
    while S2[-1]!=flagpoint:
        S2.append((FROM[S2[-1]]))

    #print(S1,S2)

    ROOP=S1+S2[1:-1]
    #print(ROOP)

    score=0
    ind=0

    NOW=flagpoint
    for ind in range(len(ROOP)):
        for to,c in E[ROOP[ind-1]]:
            if to==ROOP[ind]:
                score+=c*(-1)**(ind%2)
                break
        #print(score)
    #print(score)

    if score%2!=0 or score<0:
        print(0)
        sys.exit()

    ANS=[-1]*(n+1)
        
    ANS[flagpoint]=score//2

    Q=[flagpoint]
    USE=[0]*(n+1)

    while Q:
        x=Q.pop()
        for to,c in E[x]:
            if USE[to]==0:
                USE[to]=1
                ANS[to]=c-ANS[x]
                Q.append(to)

    flag=1
    for i in range(n+1):
        for to,c in E[i]:
            if ANS[to]+ANS[i]!=c:
                flag=0
                print(0)
                sys.exit()

    print(1)
    sys.exit()

Q=[1]
score=[-1<<31]*(n+1)
score[1]=0
while Q:
    x=Q.pop()
    for to,c in E[x]:
        if score[to]==-1<<31:
            score[to]=c-score[x]
            Q.append(to)
        else:
            if score[to]!=c-score[x]:
                print(0)
                sys.exit()

MIN0=0
MIN1=1<<31

for i in range(1,n+1):
    if USE[i]==0:
        MIN0=min(MIN0,score[i])
    else:
        MIN1=min(MIN1,score[i])

#print(MIN0,MIN1)
print(max(0,max(0,MIN1)+MIN0-1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())

E=[[] for i in range(n+1)]

for i in range(m):
    x,y,s=map(int,input().split())
    E[x].append((y,s))
    E[y].append((x,s))

Q=[1]
USE=[-1]*(n+1)
USE[1]=0
FROM=[-1]*(n+1)

flag=1
while Q and flag==1:
    x=Q.pop()
    for to,c in E[x]:
        if USE[to]==USE[x]:
            flag=0
            flagpoint=to
            break
        if USE[to]==-1:
            Q.append(to)
            USE[to]=1-USE[x]
            FROM[to]=x

if flag==0:
    Q=[flagpoint]
    FROM=[-1]*(n+1)
    FROM[flagpoint]=-5
    USE=[-1]*(n+1)
    USE[flagpoint]=0
    flag=1
    while Q and flag==1:
        x=Q.pop()

        for to,c in E[x]:
            if USE[to]==USE[x]:
                flag=0
                break

            if FROM[to]==-1:
                Q.append(to)
                FROM[to]=x
                USE[to]=1-USE[x]

    S1=[to,x]
    while S1[-1]!=flagpoint:
        S1.append((FROM[S1[-1]]))

    S2=[to]
    while S2[-1]!=flagpoint:
        S2.append((FROM[S2[-1]]))

    #print(S1,S2)

    ROOP=S1+S2[1:-1]
    #print(ROOP)

    score=0
    ind=0

    NOW=flagpoint
    for ind in range(len(ROOP)):
        for to,c in E[ROOP[ind-1]]:
            if to==ROOP[ind]:
                score+=c*(-1)**(ind%2)
                break
        #print(score)
    #print(score)

    if score%2!=0:
        print(0)
        sys.exit()

    ANS=[-1]*(n+1)
        
    ANS[flagpoint]=score//2

    Q=[flagpoint]
    USE=[0]*(n+1)

    while Q:
        x=Q.pop()
        for to,c in E[x]:
            if USE[to]==0:
                USE[to]=1
                ANS[to]=c-ANS[x]
                Q.append(to)

    flag=1
    for i in range(n+1):
        for to,c in E[i]:
            if ANS[to]+ANS[i]!=c:
                flag=0
                print(0)
                sys.exit()

    print(1)
    sys.exit()

Q=[1]
score=[-1<<31]*(n+1)
score[1]=0
while Q:
    x=Q.pop()
    for to,c in E[x]:
        if score[to]==-1<<31:
            score[to]=c-score[x]
            Q.append(to)
        else:
            if score[to]!=c-score[x]:
                print(0)
                sys.exit()

MIN0=0
MIN1=1<<31

for i in range(1,n+1):
    if USE[i]==0:
        MIN0=min(MIN0,score[i])
    else:
        MIN1=min(MIN1,score[i])

#print(MIN0,MIN1)
print(max(0,max(0,MIN1)+MIN0-1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())

E=[[] for i in range(n+1)]

for i in range(m):
    x,y,s=map(int,input().split())
    E[x].append((y,s))
    E[y].append((x,s))

Q=[1]
USE=[-1]*(n+1)
USE[1]=0
FROM=[-1]*(n+1)

flag=1
while Q and flag==1:
    x=Q.pop()
    for to,c in E[x]:
        if USE[to]==USE[x]:
            flag=0
            flagpoint=to
            break
        if USE[to]==-1:
            Q.append(to)
            USE[to]=1-USE[x]
            FROM[to]=x

if flag==0:
    Q=[flagpoint]
    FROM=[-1]*(n+1)
    FROM[flagpoint]=-5
    USE=[-1]*(n+1)
    USE[flagpoint]=0
    flag=1
    while Q and flag==1:
        x=Q.pop()

        for to,c in E[x]:
            if USE[to]==USE[x]:
                flag=0
                break

            if FROM[to]==-1:
                Q.append(to)
                FROM[to]=x
                USE[to]=1-USE[x]

    S1=[to,x]
    while S1[-1]!=flagpoint:
        S1.append((FROM[S1[-1]]))

    S2=[to]
    while S2[-1]!=flagpoint:
        S2.append((FROM[S2[-1]]))

    #print(S1,S2)

    ROOP=S1+S2[1:-1]
    #print(ROOP)

    score=0
    ind=0

    NOW=flagpoint
    for ind in range(len(ROOP)):
        for to,c in E[ROOP[ind-1]]:
            if to==ROOP[ind]:
                score+=c*(-1)**(ind%2)
                break
        #print(score)
    #print(score)

    if score%2!=0:
        print(0)
        sys.exit()

    ANS=[-1]*(n+1)
        
    ANS[flagpoint]=score//2

    Q=[flagpoint]
    USE=[0]*(n+1)

    while Q:
        x=Q.pop()
        for to,c in E[x]:
            if USE[to]==0:
                USE[to]=1
                ANS[to]=c-ANS[x]
                Q.append(to)

    flag=1
    for i in range(n+1):
        for to,c in E[i]:
            if ANS[to]+ANS[i]!=c:
                flag=0
                print(0)
                sys.exit()

    print(1)
    sys.exit()

Q=[1]
score=[-1<<31]*(n+1)
score[1]=0
while Q:
    x=Q.pop()
    for to,c in E[x]:
        if score[to]==-1<<31:
            score[to]=c-score[x]
            Q.append(to)
        else:
            if score[to]!=c-score[x]:
                print(0)
                sys.exit()

MIN0=0
MIN1=1<<31

for i in range(1,n+1):
    if USE[i]==0:
        MIN0=min(MIN0,score[i])
    else:
        MIN1=min(MIN1,score[i])

#print(MIN0,MIN1)
print(max(0,MIN1+MIN0-1))

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
VUS = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

# plot_graph(VUS)

# 解説
graph = [[] for _ in range(N)]
for v, u, s in VUS:
    v -= 1
    u -= 1
    graph[v].append((u, s))
    graph[u].append((v, s))


def test():
    mi = 1
    ma = INF
    for _, w in graph[0]:
        ma = min(ma, w - 1)

    ret = 0
    for s in range(mi, ma + 1):
        ns = [None] * N
        ns[0] = s
        stack = [(0, None)]
        ok = True
        while stack:
            v, p = stack.pop()
            for u, w in graph[v]:
                if u == p:
                    continue
                if ns[u] == w - ns[v]:
                    continue
                if ns[u] is not None:
                    ok = False
                    break
                if w - ns[v] <= 0:
                    ok = False
                    break
                ns[u] = w - ns[v]
                stack.append((u, v))
        ret += ok
    print(ret)


def solve():
    odd_diffs = [None] * N
    even_diffs = [None] * N

    s = 0
    even_diffs[0] = s
    stack = [(0, s, None, True)]
    while stack:
        v, d, p, v_even = stack.pop()
        next_diffs = (odd_diffs, even_diffs)[not v_even]
        for u, w in graph[v]:
            if u == p:
                continue
            next_d = w - d
            if next_diffs[u] == next_d:
                continue
            elif next_diffs[u] is None:
                next_diffs[u] = next_d
                stack.append((u, next_d, v, not v_even))
            else:
                # 矛盾
                return 0

    # 頂点0をsとして、sの最大値最小値を求める
    ma = IINF
    mi = 1
    for v in range(N):
        # 隣接する辺の重さの最小値
        w = INF
        for _, dw in graph[v]:
            w = min(w, dw)
        od = odd_diffs[v]
        ed = even_diffs[v]
        if od is not None and ed is not None:
            # 条件が2つある
            # od - s == ed + s
            # s == (od - ed) // 2
            if (od - ed) % 2 != 0:
                return 0
            ma = min(ma, (od - ed) // 2)
            mi = max(mi, (od - ed) // 2)
        elif od is not None:
            # vまでの距離が奇数のとき
            # 0 < d - s < w
            # d - w < s < d
            ma = min(ma, od - 1)
            mi = max(mi, od - w + 1)
        elif ed is not None:
            # vまでの距離が偶数のとき
            # 0 < d + s < w
            # -d < s < w - d
            ma = min(ma, w - ed - 1)
            mi = max(mi, -ed + 1)
    return max(0, ma - mi + 1)


ans = solve()
print(ans)

# test()