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:
#(x,y)...xt+yが書かれる
from collections import deque
N,M=map(int,input().split())
G=[{} for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    u-=1;v-=1
    G[u][v]=s;G[v][u]=s
H=[(0,0) for i in range(N)]
t=None
q=deque([0])
H[0]=(1,0)
while(q):
    r=q.pop()
    for p in G[r]:
        s=G[r][p]
        tmp=(-H[r][0],s-H[r][1])
        if H[p]==(0,0):
            H[p]=tmp
            q.append(p)
        elif H[p]==tmp:
            pass
        else:
            if H[p][0]==tmp[0]:
                print(0)
                exit()
            else:
                a=H[p][1]
                b=tmp[1]
                if H[p][0]==-1:
                    a,b=b,a
                #t+a=-t+b
                #2t=b-a
                if (b-a)%2:
                    print(0)
                    exit()
                else:
                    t=(b-a)//2
'''
t+a>=0:t>=-a
-t+b>=0:t<=b
inf=max(a)
sup=min(b)
'''
if t==None:
    inf=-10**18
    sup=10**18
    for i in range(N):
        if H[i][0]==1:
            inf=max(inf,-H[i][1])
        else:
            sup=min(sup,H[i][1])
    print(max(sup-inf-1,0))
else:
    flag=1
    q=deque([0])
    reached=[0 for i in range(N)]
    while(q and flag):
        r=q.pop()
        reached[r]=1
        for p in G[r]:
            if H[r][0]*t+H[r][1]+H[p][0]*t+H[p][1]==G[p][r]:
                pass
            else:
                flag=0
                break
            if reached[p]==0:
                q.append(p)
    if flag:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
#(x,y)...xt+yが書かれる
from collections import deque
N,M=map(int,input().split())
G=[{} for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    u-=1;v-=1
    G[u][v]=s;G[v][u]=s
H=[(0,0) for i in range(N)]
t=None
q=deque([0])
H[0]=(1,0)
while(q):
    r=q.pop()
    for p in G[r]:
        s=G[r][p]
        tmp=(-H[r][0],s-H[r][1])
        if H[p]==(0,0):
            H[p]=tmp
            q.append(p)
        elif H[p]==tmp:
            pass
        else:
            if H[p][0]==tmp[0]:
                print(0)
                exit()
            else:
                a=H[p][1]
                b=tmp[1]
                if H[p][0]==-1:
                    a,b=b,a
                #t+a=-t+b
                #2t=b-a
                if (b-a)%2:
                    print(0)
                    exit()
                else:
                    t=(b-a)//2
'''
t+a>=0:t>=-a
-t+b>=0:t<=b
inf=max(a)
sup=min(b)
'''
if t==None:
    inf=0
    sup=10**15
    for i in range(N):
        if H[i][0]==1:
            inf=max(inf,-H[i][1])
        else:
            sup=min(sup,H[i][1])
    print(max(sup-inf-1,0))
else:
    flag=1
    for i in range(N):
        for j in G[i]:
            if (t*H[i][0]+H[i][1])+(t*H[j][0]+H[j][1])==G[i][j]:
                pass
            else:
                flag=0
                break
    if flag:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append((c,v))
    ns[v].append((c,u))
seen = [None]*n
q = [(0,-1)]
seen[0] = (1,0) # (符号, 値) x+val
done = False
ans = None
X = None
while q:
    u,prv = q.pop()
    for c,v in ns[u]:
        if v==prv:
            continue
        if seen[v] is not None:
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            sv,vv = seen[v]
            if su==sv:
                if vu!=vv:
                    ans = 0
                    break
                else:
                    pass
            else:
                done = True
                d,m = divmod(vv-vu, su-sv)
                if m!=0:
                    ans = 0
                    break
                if X is None:
                    X = d
                elif X!=d:
                    ans = 0
                    break
        else:
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            seen[v] = (su, vu)
            q.append((v,u))
    if ans is not None:
        break
if ans is not None:
    print(ans)
elif done:
    if X>0:
        print(1)
    else:
        print(0)
else:
    lb = 1
    ub = 10**10
    for s,v in seen:
        if s==1:
            lb = max(lb, 1-v)
        else:
            ub = min(ub, v-1)
    if lb>ub:
        print(0)
    else:
        print(ub-lb+1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append((c,v))
    ns[v].append((c,u))
seen = [None]*n
q = [(0,-1)]
seen[0] = (1,0) # (符号, 値) x+val
done = False
ans = None
X = None
while q:
    u,prv = q.pop()
    for c,v in ns[u]:
        if v==prv:
            continue
        if seen[v] is not None:
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            sv,vv = seen[v]
            if su==sv:
                if vu!=vv:
                    ans = 0
                    break
                else:
                    pass
            else:
                done = True
                d,m = divmod(vv-vu, su-sv)
                if m!=0:
                    ans = 0
                    break
                if X is None:
                    X = d
                elif X!=d:
                    ans = 0
                    break
        else:
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            seen[v] = (su, vu)
            q.append((v,u))
    if ans is not None:
        break
if ans is not None:
    print(ans)
elif done:
    print(1)
else:
    lb = 1
    ub = 10**10
    for s,v in seen:
        if s==1:
            lb = max(lb, 1-v)
        else:
            ub = min(ub, v-1)
    if lb>ub:
        print(0)
    else:
        print(ub-lb+1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append((c,v))
    ns[v].append((c,u))
seen = [None]*n
q = [(0,-1)]
seen[0] = (1,0) # (符号, 値) x+val
done = False
ans = None
X = None
add = []
while q:
    u,prv = q.pop()
    for c,v in ns[u]:
        if v==prv:
            continue
        if seen[v] is not None:
            done = True
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            sv,vv = seen[v]
            if su==sv:
                if vu!=vv:
                    ans = 0
                    break
                else:
                    pass
            else:
                d,m = divmod(vv-vu, su-sv)
                if m!=0:
                    ans = 0
                    break
                if X is None:
                    X = d
                elif X!=d:
                    ans = 0
                    break
                add.append((sv, vv))
        else:
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            seen[v] = (su, vu)
            q.append((v,u))
    if ans is not None:
        break
if ans is not None:
    print(ans)
elif done:
    print(1)
else:
    lb = 1
    ub = 10**10
    for s,v in seen+add:
        if s==1:
            lb = max(lb, 1-v)
        else:
            ub = min(ub, v-1)
    if lb>ub:
        print(0)
    else:
        print(ub-lb+1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append((c,v))
    ns[v].append((c,u))
seen = [None]*n
q = [(0,-1)]
seen[0] = (1,0) # (符号, 値) x+val
done = False
ans = None
X = None
while q:
    u,prv = q.pop()
    for c,v in ns[u]:
        if v==prv:
            continue
        if seen[v] is not None:
            done = True
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            sv,vv = seen[v]
            if su==sv:
                if vu!=vv:
                    ans = 0
                    break
                else:
                    pass
            else:
                d,m = divmod(vv-vu, su-sv)
                if m!=0:
                    ans = 0
                    break
                if X is None:
                    X = d
                elif X!=d:
                    ans = 0
                    break
        else:
            su,vu = seen[u]
            su *= -1
            vu = c - vu
            seen[v] = (su, vu)
            q.append((v,u))
    if ans is not None:
        break
if ans is not None:
    print(ans)
elif done:
    print(1)
else:
    lb = 1
    ub = 10**10
    for s,v in seen:
        if s==1:
            lb = max(lb, 1-v)
        else:
            ub = min(ub, v-1)
    if lb>ub:
        print(0)
    else:
        print(ub-lb+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
G=[{} for _ in range(n)]

for i in range(m):
  u,v,s=map(int,input().split())
  G[u-1][v-1] = G[v-1][u-1] = s

dp = [[0]*n for _ in range(2)]
start=0
l,r = 1,min(G[start].values())
dp[0][start] = l
dp[1][start] = r

def bfs(s):
    seen = [0]*n
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          dp[0][b] = max(G[a][b]-dp[1][a],1)
          dp[1][b] = G[a][b]-dp[0][a]
          if dp[1][b]<1:
            print(0)
            exit()
        else:
          dp[0][b] = max(dp[0][b],max(G[a][b]-dp[1][a],1))
          dp[1][b] = min(dp[1][b],G[a][b]-dp[0][a])
          if dp[0][b]>dp[1][b] or dp[1][b]<1:
            print(0)
            exit()
    return
  
for i in range(3):
  bfs(start)

print(min([dp[1][i]-dp[0][i]+1 for i in range(n)]))

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
G=[{} for _ in range(n)]

for i in range(m):
  u,v,s=map(int,input().split())
  G[u-1][v-1] = G[v-1][u-1] = s

dp = [[0]*n for _ in range(2)]
start=0
l,r = 1,min(G[start].values())
dp[0][start] = l
dp[1][start] = r

def bfs(s):
    seen = [0]*n
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          dp[0][b] = max(G[a][b]-dp[1][a],1)
          dp[1][b] = G[a][b]-dp[0][a]
          if dp[1][b]<1:
            print(0)
            exit()
        else:
          dp[0][b] = max(dp[0][b],max(G[a][b]-dp[1][a],1))
          dp[1][b] = min(dp[1][b],G[a][b]-dp[0][a])
          if dp[0][b]>dp[1][b] or dp[1][b]<1:
            print(0)
            exit()
    return
  
bfs(start)

print(min([dp[1][i]-dp[0][i]+1 for i in range(n)]))

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
G=[{} for _ in range(n)]

for i in range(m):
  u,v,s=map(int,input().split())
  G[u-1][v-1] = G[v-1][u-1] = s

dp = [[0]*n for _ in range(2)]
start=0
l,r = 1,min(G[start].values())
dp[0][start] = l
dp[1][start] = r

def bfs(s):
    seen = [0]*n
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a].keys():
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          dp[0][b] = max(G[a][b]-dp[1][a],1)
          dp[1][b] = G[a][b]-dp[0][a]
          if dp[1][b]<1:
            print(0)
            exit()
        else:
          dp[0][b] = max(dp[0][b],max(G[a][b]-dp[1][a],1))
          dp[1][b] = min(dp[1][b],G[a][b]-dp[0][a])
          if dp[1][b]<1:
            print(0)
            exit()
    return
  
bfs(start)

print(min([dp[1][i]-dp[0][i]+1 for i in range(n)]))

Submission status: Wrong Answer

Solution code:
# 【条件1】各ノードに記載する数字が全部正の整数
# start: v (> 0) として
# 1: s1 - v > 0            =>  s1 > v
# 2: s2 - s1 + v > 0       =>  v > s1 - s2
# 3: s3 - s2 + s1 - v > 0  =>  s1 - s2 + s3 > v
# 4: ...
# -> max{0, s1 - s2, s1 - s2 + s3 - s4, ...} < v < min{s1, s1 - s2 + s3, ...}
#    なので、max{0, 右辺 - 左辺 - 1} が答え。
# 【条件2】 loopがあったらそのloop上で s1 - s2 + s3 - s4 + ... = 0 じゃないとダメ
# あるノードまで複数の行き方で行けた場合
#   s1 - s2 + s3 - ... = s'1 - s'2 + s'3 - ...
# が成り立っていれば整合性は保たれる。
from collections import defaultdict, deque


def main():
    INF = 10 ** 15
    N, M = map(int, input().split())
    S = defaultdict(int)
    adj = defaultdict(list)
    for _ in range(M):
        u, v, s = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
        S[(u, v)], S[(v, u)] = s, s
    even_sum_s, odd_sum_s = [- INF] * N, [INF] * N
    start = 0
    even_sum_s[start] = 0
    que = deque([(start, -1, 0, 0)])  # (node, parent, dist from start, sum of signed `s`)
    # DFS
    while len(que) > 0:
        node, parent_node, dist, sum_s = que.pop()
        for next_node in adj[node]:
            if parent_node == next_node:
                continue
            next_dist = dist + 1
            if next_dist % 2 == 1:
                next_sum_s = sum_s + S[(node, next_node)]
                if odd_sum_s[next_node] == INF:
                    odd_sum_s[next_node] = next_sum_s
                    que.append((next_node, node, next_dist, next_sum_s))
                else:
                    if odd_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
            else:
                next_sum_s = sum_s - S[(node, next_node)]
                if even_sum_s[next_node] == - INF:
                    even_sum_s[next_node] = next_sum_s
                    que.append((next_node, node, next_dist, next_sum_s))
                else:
                    if even_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
    lower, upper = max(even_sum_s), min(odd_sum_s)
    print(max(0, upper - lower - 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 【条件1】各ノードに記載する数字が全部正の整数
# start: v (> 0) として
# 1: s1 - v > 0            =>  s1 > v
# 2: s2 - s1 + v > 0       =>  v > s1 - s2
# 3: s3 - s2 + s1 - v > 0  =>  s1 - s2 + s3 > v
# 4: ...
# -> max{0, s1 - s2, s1 - s2 + s3 - s4, ...} < v < min{s1, s1 - s2 + s3, ...}
#    なので、max{0, 右辺 - 左辺 - 1} が答え。
# 【条件2】 loopがあったらそのloop上で s1 - s2 + s3 - s4 + ... = 0 じゃないとダメ
# あるノードまで複数の行き方で行けた場合
#   s1 - s2 + s3 - ... = s'1 - s'2 + s'3 - ...
# が成り立っていれば整合性は保たれる。
from collections import defaultdict, deque


def main():
    INF = 10 ** 15
    N, M = map(int, input().split())
    S = defaultdict(int)
    adj = defaultdict(list)
    for _ in range(M):
        u, v, s = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
        S[(u, v)], S[(v, u)] = s, s
    even_sum_s, odd_sum_s = [- INF] * N, [INF] * N
    start = 0
    even_sum_s[start] = 0
    que = deque([(start, 0, 0)])  # (node, dist from start, sum of signed `s`)
    # DFS
    while len(que) > 0:
        node, dist, sum_s = que.pop()
        for next_node in adj[node]:
            next_dist = dist + 1
            if next_dist % 2 == 1:
                next_sum_s = sum_s + S[(node, next_node)]
                if odd_sum_s[next_node] == INF:
                    odd_sum_s[next_node] = next_sum_s
                    que.append((next_node, next_dist, next_sum_s))
                else:
                    if odd_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
            else:
                next_sum_s = sum_s - S[(node, next_node)]
                if even_sum_s[next_node] == - INF:
                    even_sum_s[next_node] = next_sum_s
                    que.append((next_node, next_dist, next_sum_s))
                else:
                    if even_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
    lower, upper = max(even_sum_s), min(odd_sum_s)
    print(max(0, upper - lower - 1))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        u,v,s=MI()
        u-=1
        v-=1
        adj[u].append((v,s))
        adj[v].append((u,s))
    
    #　頂点0を根として，ここの値aとする，各頂点Xa+Cの形で表して，最大値と最小値の候補を絞っていく．ループがあるかをしっかり判断
    
    # Xはaの係数，1orー１が入る．0ならまだ見ていない
    X=[0]*N
    C=[0]*N
    
    X[0]=1
    
    floor=1
    ceil=10**9
    
    import queue
    q=queue.Queue()
    q.put((0,-1))#v,p
    
    while not q.empty():
        v,p=q.get()
        
        
        for nv,s in adj[v]:
            if nv!=p:
                if X[nv]==0:
                    q.put((nv,v))
                nx=X[v]*(-1)
                nc=s-C[v]
                
                #見巡回の頂点なら
                if X[nv]==0 and C[nv]==0:
                    X[nv]=nx
                    C[nv]=nc
                    
                    # aの係数が正ならば，下限を更新
                    if nx==1:
                        floor=max(floor,-1*nc)
                        
                    #aの係数が負ならば上限を更新
                    else:
                        ceil=min(ceil,nc-1)
                        
                else:
                    # 既存のものと変わらなければ何もしない
                    if nx==X[nv] and nc==C[nv]:
                        pass
                    #係数が同じで定数部分が違えば無理
                    elif nx==X[nv]:
                        ceil=-1
                    #係数が違う場合，一意に決まる
                    else:
                        ac=0#係数が正の方の定数
                        bc=0#係数が負の方の定数
                        if nx==1:
                            ac=nc
                            bc=C[nv]
                        else:
                            ac=C[nv]
                            bc=nc
                        
                        # 2*aの値
                        aa=bc-ac
                        
                        if aa<=0 or aa%2==1:
                            ceil=-1
                        else:
                            ceil=ceil=min(ceil,aa//2)
                            floor=max(floor,aa//2)
                #print(nv,floor,ceil)
                            
    ans=ceil-floor+1
    if ans<=0:
        ans=0
    print(ans)
    
    
                            

                        
    

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        u,v,s=MI()
        u-=1
        v-=1
        adj[u].append((v,s))
        adj[v].append((u,s))
    
    #　頂点0を根として，ここの値aとする，各頂点Xa+Cの形で表して，最大値と最小値の候補を絞っていく．ループがあるかをしっかり判断
    
    # Xはaの係数，1orー１が入る．0ならまだ見ていない
    X=[0]*N
    C=[0]*N
    
    X[0]=1
    
    floor=1
    ceil=10**9
    
    import queue
    q=queue.Queue()
    q.put((0,-1))#v,p
    
    while not q.empty():
        v,p=q.get()
        for nv,s in adj[u]:
            if nv!=p:
                nx=X[v]*(-1)
                nc=s-C[v]
                
                #見巡回の頂点なら
                if X[nv]==0 and C[nv]==0:
                    X[nv]=nx
                    C[nv]=nc
                    
                    # aの係数が正ならば，下限を更新
                    if nx==1:
                        floor=max(floor,-1*nc)
                        
                    #aの係数が負ならば上限を更新
                    else:
                        ceil=min(ceil,nc-1)
                        
                else:
                    # 既存のものと変わらなければ何もしない
                    if nx==X[nv] and nc==C[nv]:
                        pass
                    #係数が同じで定数部分が違えば無理
                    elif nx==X[nv]:
                        ceil=-1
                    #係数が違う場合，一意に決まる
                    else:
                        ac=0#係数が正の方の定数
                        bc=0#係数が負の方の定数
                        if nx==1:
                            ac=nc
                            bc=C[nv]
                        else:
                            ac=C[nv]
                            bc=nc
                        
                        # 2*aの値
                        aa=bc-ac
                        
                        if aa<=0 or aa%2==1:
                            ceil=-1
                        else:
                            ceil=ceil=min(ceil,aa//2)
                            floor=max(floor,aa//2)
                            
    ans=ceil-floor
    if ans<=0:
        ans=0
    print(ans)
    
                            

                        
    

main()

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
print(-1)
print(max(ma - mi + 1, 0) if x == -1 else 1)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            # if val[u][1] + val[v][1] != s:
            #     print(0)
            #     exit()
            pass
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
print(max(ma - mi + 1, 0) if x == -1 else 1)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            # elif x != b // 2:
            #     print(0)
            #     exit()
print(max(ma - mi + 1, 0) if x == -1 else 1)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            # elif x != b // 2:
            #     print(0)
            #     exit()
print(max(ma - mi + 1, 0) if x == -1 else 1)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            # elif x != b // 2:
            #     print(0)
            #     exit()
print(max(ma - mi + 1, 0) if x == -1 else 1)

Submission status: Wrong Answer

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v] is None:
            val[v] = (-val[u][0], s - val[u][1])
            queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            # if b <= 0 or b % 2 == 1:
            #     print(0)
            #     exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
if x != -1:
    print(1)
else:
    print(max(ma - mi + 1, 0))