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:
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, s))
    edges[v].append((u, s))

visited = [False] * n
visited[0] = True
mem = [[] for _ in range(n)]
mem[0].append((0, False))
stack = []
stack.append((0, 0, False))
while stack:
    node, score, turn = stack.pop()
    for to, s in edges[node]:
        if not visited[to]:
            visited[to] = True
            mem[to].append((s - score, not turn))
            stack.append((to, s - score, not turn))
        else:
            mem[to].append((s - score, not turn))

h, l = 10 ** 20, 10 ** 20
decide = None
for lst in mem:
    trues = set()
    falses = set()
    for v, f in lst:
        if f:
            trues.add(v)
        else:
            falses.add(v)
    if len(trues) >= 2 or len(falses) >= 2:
        print(0)
        break

    elif len(trues) == len(falses) == 1:
        _a = list(trues)[0] - list(falses)[0]
        if _a >= 2 and _a % 2 == 0:
            a = _a // 2
            if decide == None:
                decide = a
            elif decide != a:
                print(0)
                break

        else:
            print(0)
            break

    elif len(trues) == 1:
        h = min(h, list(trues)[0])
    elif len(falses) == 1:
        l = min(l, list(falses)[0])

else:
    if decide != None:
        print(1)
    else:
        if (h + l - 1) > 0:
            print(h + l - 1)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, s))
    edges[v].append((u, s))

visited = [False] * n
visited[0]  = True
lowMem = [None] * n
lowMem[0] = 0
highMem = [None] * n
decide = None
stack = []
stack.append((0, 0, 0))
outFlag = False
while stack and not outFlag:
    node, score, turn = stack.pop()
    for to, s in edges[node]:
        if not visited[to]:
            visited[to] = True

            if turn == 0:
                highMem[to] = s - score
                stack.append((to, s - score, 1))
            else:
                lowMem[to] = s - score
                stack.append((to, s - score, 0))

        else:
            if highMem[to] != None:
                if turn == 0:
                    if highMem[to] == s - score:
                        continue
                    else:
                        outFlag = True
                        break

                else:
                    if highMem[to] - s + score >= 2 and (highMem[to] - s + score) % 2 == 0:
                        ans = (highMem[to] - s + score) // 2
                        if decide == None:
                            decide = ans
                        elif decide != ans:
                            outFlag = True
                            break
                    else:
                        outFlag = True
                        break

            else:
                if turn == 0:
                    if s - score - lowMem[to] >= 2 and (s - score - lowMem[to]) % 2 == 0:
                        ans = (s - score - lowMem[to]) // 2
                        if decide == None:
                            decide = ans
                        elif decide != ans:
                            outFlag = True
                            break
                    else:
                        outFlag = True
                        break


                else:
                    if lowMem[to] == s - score:
                        continue
                    else:
                        outFlag = True
                        break


if outFlag:
    print(0)
elif decide != None:
    print(1)
else:
    h = 10 ** 20
    for x in highMem:
        if x != None and h > x:
            h = x

    l = 10 ** 20
    for x in lowMem:
        if x != None and l > x:
            l = x
    
    if h + l - 1 > 0:
        print(h + l - 1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, s))
    edges[v].append((u, s))

visited = [False] * n
visited[0]  = True
lowMem = [None] * n
lowMem[0] = 0
highMem = [None] * n
decide = None
stack = []
stack.append((0, 0, 0))
outFlag = False
while stack and not outFlag:
    node, score, turn = stack.pop()
    for to, s in edges[node]:
        if not visited[to]:
            visited[to] = True

            if turn == 0:
                highMem[to] = s - score
                stack.append((to, s - score, 1))
            else:
                lowMem[to] = s - score
                stack.append((to, s - score, 0))

        else:
            if highMem[to] != None:
                if turn == 0:
                    if highMem[to] == s - score:
                        continue
                    else:
                        outFlag = True
                        break

                else:
                    if highMem[to] - s + score >= 2 and (highMem[to] - s + score) % 2 == 0:
                        ans = (highMem[to] - s + score) // 2
                        if decide == None:
                            decide = ans
                        elif decide != ans:
                            outFlag = True
                            break
                    else:
                        outFlag = True
                        break

            else:
                if turn == 0:
                    if s - score - lowMem[to] >= 2 and (s - score - lowMem[to]) % 2 == 0:
                        ans = (s - score - lowMem[to]) // 2
                        if decide == None:
                            decide = ans
                        elif decide != ans:
                            outFlag = True
                            break
                    else:
                        outFlag = True
                        break


                else:
                    if lowMem[to] == s - score:
                        continue
                    else:
                        outFlag = True
                        break


if outFlag:
    print(0)
elif decide != None:
    print(1)
else:
    h = 10 ** 20
    for x in highMem:
        if x != None and h > x:
            h = x

    l = 0
    for x in lowMem:
        if x != None and l > x:
            l = x
    
    if h + l - 1 > 0:
        print(h + l - 1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N, M = map(int, input().split())
table = [[] for i in range(N)]
for i in range(M):
    u, v, s = map(int, input().split())
    table[u - 1].append((v - 1, s))
    table[v - 1].append((u - 1, s))
L = [0] * N
T = [1] * N  # checker
visit = [False] * N
h = deque()
h.append([0, 1])
visit[0] = True
flag = True

K = []

while h:
    x, t = h.popleft()
    for y, s in table[x]:
        if visit[y]:
            if T[y] == T[x]:
                flag = False
                K.append((x, y, s))
            else:
                if L[y] + L[x] != s:
                    print(0)
                    sys.exit()
            continue
        T[y] = -t
        visit[y] = True
        L[y] = s - L[x]
        h.append([y, -t])

if not flag:
    x, y, s = K[0]
    t = T[x]
    u = L[x] + L[y] - s
    if u % 2 != 0:
        print(0)
        sys.exit()
    u = u // 2
    for i in range(N):
        if T[i] == t:
            L[i] -= u
        else:
            L[i] += u
    for x, y, s in K:
        if L[x] + L[y] != s:
            print(0)
            sys.exit()
    print(1)
    sys.exit()
a = 10 ** 13
c = 10 ** 13
# b=-10**13
# d=-10**13
for i in range(N):
    if T[i] == 1:
        a = min(a, L[i])
        # b=max(b,L[i])
    else:
        c = min(c, L[i])
        # d=max(d,L[i])
print(max(0, c + a - 1))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
G=[dict() for i in range(N)]
U=[0 for i in range(M)]
V=[0 for i in range(M)]
S=[0 for i in range(M)]
for i in range(M):
    U[i],V[i],S[i]=map(int,input().split())
    G[U[i]-1][V[i]-1]=S[i]
    G[V[i]-1][U[i]-1]=S[i]
    U[i]-=1
    V[i]-=1
H=[set() for i in range(N)]
reached=[0 for i in range(N)]
q=[]
q.append(0)
H[0].add((0,1))
def check(SET):
    X=set()
    Y=set()
    for i in SET:
        if i[1]==1:
            X.add(i[0])
        else:
            Y.add(i[0])
    if len(X)>=2 or len(Y)>=2:
        print(0)
        exit()
    elif len(X)==0 or len(Y)==0:
        return None
    else:
        a=list(X)[0]
        b=list(Y)[0]
        T=(a+b)//2
        if (a+b)%2==1:
            print(0)
            exit()
        else:
            I=[0 for i in range(N)]
            I[0]=T
            q1=[]
            q1.append(0)
            rcd=[0 for i in range(N)]
            while(len(q1)>0):
                r1=q1[-1]
                q1.pop()
                for p1 in G[r1]:
                    if reached[p1]==1:
                        continue
                    I[p1]=G[r1][p1]-I[r1]
                    reached[p1]==1
                    q1.put(p1)
            if min(I)<=0:
                print(0)
                exit()
            for k in range(M):
                if I[U[k]]+I[V[k]]!=S[k]:
                    print(0)
                    exit()
            return None
                    
while(len(q)>0):
    r=q[-1]
    q.pop()
    for p in G[r]:
        if reached[p]==1:
            continue
        reached[p]=1
        q.append(p)
        check(H[r])
        for s in H[r]:
            H[p].add((G[r][p]-s[0],-s[1]))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            #continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
if (c -t)%2==1:
    print(0)
    sys.exit()
w=(c-t)//2
dp=[inf]*N
if s==0:
    dp[0]=w
else:
    dp[0]=-w

k=deque()
k.append(0)
while k:
    x =k.popleft()
    for y,d in table[x]:
        if dp[y]!=inf and (dp[x]+dp[y])!=d:
            print(0)
            sys.exit()
        if dp[y]==inf:
            dp[y]=d-dp[x]
            k.append(y)
for i in range(N):
    if dp[i]<=0:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            #continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
#if (c -t)%2==1:
    #print(0)
    #sys.exit()
w=(c-t)//2
dp=[inf]*N
if s==0:
    dp[0]=w
else:
    dp[0]=-w

k=deque()
k.append(0)
while k:
    x =k.popleft()
    for y,d in table[x]:
        if dp[y]!=inf and (dp[x]+dp[y])!=d:
            print(0)
            sys.exit()
        if dp[y]==inf:
            dp[y]=d-dp[x]
            k.append(y)
for i in range(N):
    if dp[i]<=0:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            #continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
#if (c -t)%2==1:
    #print(0)
    #sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
for i in range(N):
    if visit[i][0]<=0:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
#if (c -t)%2==1:
    #print(0)
    #sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
for i in range(N):
    if visit[i][0]<=0:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.pop()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
#if (c -t)%2==1:
    #print(0)
    #sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
for i in range(N):
    if visit[i][0]<=0:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.pop()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
#if (c -t)%2==1:
    #print(0)
    #sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
for i in range(N):
    if visit[i][0]==0:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.pop()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
#if (c -t)%2==1:
    #print(0)
    #sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
if (c -t)%2==1:
    print(0)
    sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
if (c -t)%2==1:
    print(0)
    sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
            continue
        #if visit[y][0]!=inf:
            #continue
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
if (c -t)%2==1:
    print(0)
    sys.exit()
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in tree:
    if visit[x][0]+visit[y][0]!=d:
        print(0)
        sys.exit()
print(1)

Submission status: Wrong Answer

Solution code:
def val(siki,ans):
    return siki[0]+siki[1]*ans
n,m=list(map(int, input().strip().split()))
links=[[]for _ in range(n)]
checked={}
for i in range(m):
    u,v,s=list(map(int, input().strip().split()))
    links[u-1].append((v-1,s))
    links[v-1].append((u-1,s))
    checked[u-1,v-1]=False
    checked[v-1,u-1]=False
current=0
visited=[False]*n

sikis=[None for _ in range(n)]
sikis[0]=(0,1)
Q=[(0,l,s) for l,s in links[0]]

ans=-1
count=-1
while Q:
    u,v,cst=Q.pop()
    if checked[u,v]:continue
    visited[u]=True
    checked[u,v]=True
    checked[v,u]=True
    su = sikis[u]
    sv=(cst-su[0],su[1]*(-1))
    if not sikis[v]:
        sikis[v]=sv
        if ans>0:
            if val(sv,ans)<0:
                ans=-1
                count=0
                break
    else:
        svo=sikis[v]
        if ans > 0:
            if val(svo,ans)!=val(sv,ans):
                pass
            else:
                ans=-1
                count=0
                break
        else:
            if svo[1]==sv[1]:# 係数同じ
                if svo[0]==sv[0]:
                    pass
                else:
                    ans=-1
                    count=0
                    break
            else:# 係数違う
                if svo[1]==-1:
                    ans2=(svo[0]-sv[0])
                else:
                    ans2=(sv[0]-svo[0])
                if ans2%2!=0 or ans2<0:
                    ans=-1
                    count=0
                    break
                else:
                    ans=ans2//2
    if not visited[v]:
        for l,s in links[v]:
            if not checked[v,l]:
                Q.append([v,l,s])
if count==0:
    print(0)
elif ans>0:
    for sk in sikis:
        if val(sk,ans)<0:
            print(0)
            break
    else:
        print(1)
else:
    minnum=1
    maxnum=float("inf")
    for sk in sikis:
        if sk[1]<0:
            maxnum=min(maxnum,sk[0]-1)
        if sk[1]>0:
            minnum=max(minnum,-sk[0]+1)
    count=maxnum-minnum+1
    print(max(0,count))

Submission status: Wrong Answer

Solution code:
def val(siki,ans):
    return siki[0]+siki[1]*ans
n,m=list(map(int, input().strip().split()))
links=[[]for _ in range(n)]
checked={}
for i in range(m):
    u,v,s=list(map(int, input().strip().split()))
    links[u-1].append((v-1,s))
    links[v-1].append((u-1,s))
    checked[u-1,v-1]=False
    checked[v-1,u-1]=False
current=0
visited=[False]*n

sikis=[None for _ in range(n)]
sikis[0]=(0,1)
Q=[(0,l,s) for l,s in links[0]]

ans=-1
count=-1
while Q:
    u,v,cst=Q.pop()
    if checked[u,v]:continue
    visited[u]=True
    checked[u,v]=True
    checked[v,u]=True
    su = sikis[u]
    sv=(cst-su[0],su[1]*(-1))
    if not sikis[v]:
        sikis[v]=sv
        if ans>0:
            if sv[0]+sv[1]*ans<0:
                ans=-1
                count=0
                break
    else:
        svo=sikis[v]
        if ans > 0:
            if val(svo,ans)!=val(sv,ans):
                pass
            else:
                ans=-1
                count=0
                break
        else:
            if svo[1]==sv[1]:# 係数同じ
                if svo[0]==sv[0]:
                    pass
                else:
                    ans=-1
                    count=0
                    break
            else:# 係数違う
                if svo[1]==-1:
                    ans2=(svo[0]-sv[0])
                else:
                    ans2=(sv[0]-svo[0])
                if ans2%2!=0 or ans2<0:
                    ans=-1
                    count=0
                    break
                else:
                    ans=ans2//2
    if not visited[v]:
        for l,s in links[v]:
            if not checked[v,l]:
                Q.append([v,l,s])
if count==0:
    print(0)
elif ans>0:
    print(1)
else:
    minnum=1
    maxnum=float("inf")
    for sk in sikis:
        if sk[1]<0:
            maxnum=min(maxnum,sk[0]-1)
        if sk[1]>0:
            minnum=max(minnum,-sk[0]+1)
    count=maxnum-minnum+1
    print(max(0,count))

Submission status: Wrong Answer

Solution code:
def val(siki,ans):
    return siki[0]+siki[1]*ans
n,m=list(map(int, input().strip().split()))
links=[[]for _ in range(n)]
checked={}
for i in range(m):
    u,v,s=list(map(int, input().strip().split()))
    links[u-1].append((v-1,s))
    links[v-1].append((u-1,s))
    checked[u-1,v-1]=False
    checked[v-1,u-1]=False
current=0
visited=[False]*n

sikis=[None for _ in range(n)]
sikis[0]=(0,1)
Q=[(0,l,s) for l,s in links[0]]

ans=-1
count=-1
while Q:
    u,v,cst=Q.pop()
    if checked[u,v]:continue
    visited[u]=True
    checked[u,v]=True
    checked[v,u]=True
    su = sikis[u]
    sv=(cst-su[0],su[1]*(-1))
    if not sikis[v]:
        sikis[v]=sv
    else:
        svo=sikis[v]
        if ans > 0:
            if val(svo,ans)!=val(sv,ans):
                pass
            else:
                ans=-1
                count=0
                break
        else:
            if svo[1]==sv[1]:# 係数同じ
                if svo[0]==sv[0]:
                    pass
                else:
                    ans=-1
                    count=0
                    break
            else:# 係数違う
                if svo[1]==-1:
                    ans2=(svo[0]-sv[0])
                else:
                    ans2=(sv[0]-svo[0])
                if ans2%2!=0 or ans2<0:
                    ans=-1
                    count=0
                    break
                else:
                    ans=ans2//2
    if not visited[v]:
        for l,s in links[v]:
            if not checked[v,l]:
                Q.append([v,l,s])
if count==0:
    print(0)
elif ans>0:
    print(1)
else:
    minnum=1
    maxnum=float("inf")
    for sk in sikis:
        if sk[1]<0:
            maxnum=min(maxnum,sk[0]-1)
        if sk[1]>0:
            minnum=max(minnum,-sk[0]+1)
    count=maxnum-minnum+1
    print(max(0,count))