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 defaultdict
from queue import Queue
n,m=list(map(int, input().strip().split()))
links=[[]for _ in range(n)]
cost={}
checked={}
lnum={}
for i in range(m):
    u,v,s=list(map(int, input().strip().split()))
    links[u-1].append(v-1)
    links[v-1].append(u-1)
    cost[(u-1,v-1)]=s
    cost[(v-1,u-1)]=s
    checked[u-1,v-1]=False
    checked[v-1,u-1]=False
current=0
visited=[False]*n

class siki(object):
    def __init__(self,num,coef ):
        self.num = num
        self.coef = coef
    def val(self,ans):
        return self.num +self.coef*ans
    def __repr__(self):
        return "{}{}a".format(self.num,"-+"[self.coef>0])

sikis=[None for _ in range(n)]
sikis[0]=siki(0,1)
Q=Queue()
for l in links[0]:
    Q.put([0,l])
ans=-1
count=-1
while not Q.empty():
    u,v=Q.get()
    if checked[u,v]:continue
    visited[u]=True
    checked[u,v]=True
    checked[v,u]=True
    cst=cost[u,v]
    su = sikis[u]
    sv=siki(cst-su.num,su.coef*(-1))
    if not sikis[v]:
        sikis[v]=sv
    else:
        svo=sikis[v]
        if ans > 0:
            if svo.val(ans)!=sv.val(ans):
                pass
            else:
                ans=-1
                count=0
                break
        else:
            if svo.coef==sv.coef:# 係数同じ
                if svo.num==sv.num:
                    pass
                else:
                    ans=-1
                    count=0
                    break
            else:# 係数違う
                if svo.coef==-1:
                    ans=(svo.num-sv.num)/2
                else:
                    ans=(sv.num-svo.num)/2
                if ans!=int(ans) or ans<0:
                    print(ans)
                    ans=-1
                    count=0
                    break
                else:
                    ans=int(ans)
    if not visited[v]:
        for l in links[v]:
            if not checked[v,l]:
                Q.put([v,l])
if count==0:
    print(0)
elif ans>0:
    print(1)
else:
    minnum=1
    maxnum=float("inf")
    for sk in sikis:
        if sk.coef<0:
            maxnum=min(maxnum,sk.num-1)
        if sk.coef>0:
            minnum=max(minnum,-sk.num+1)
    print(max(0,maxnum-minnum+1))

Submission status: Wrong Answer

Solution code:
n, m =  map(int,input().split())
E = [[] for i in range(n+1)]
e0, s0, d = 0, 0, 0
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append((e[1],e[2]))
    E[e[1]].append((e[0],e[2]))
    if s0 < 1 or s0 > e[2]:
        e0 = e
        s0 = e[2]
for i in range(1, s0):
    V = [1,]+[0,]*n
    V[e0[0]] = i
    U = [e0[0],]
    while U and V[0]:
        u = U.pop()
        for e in E[u]:
            v = e[0]
            if V[v] and V[v] == e[-1] - V[u]:
                pass
            elif V[v]:break
            elif e[-1] > V[u]:
                V[v] = e[-1] - V[u]
                U += [v,]
            else:break
    d += min(V)
print(d)

Submission status: Wrong Answer

Solution code:
n, m =  map(int,input().split())
E = [[] for i in range(n+1)]
e0, s0, d = 0, 0, 0
for i in range(m):
    e = tuple(map(int,input().split()))
    E[e[0]].append((e[1],e[2]))
    E[e[1]].append((e[0],e[2]))
    if s0 < 1 or s0 > e[2]:
        e0 = e
        s0 = e[2]
for i in range(1, s0):
    V = [1,]+[0,]*n
    V[e0[0]] = i
    U = [e0[0],]
    while U and V[0]:
        u = U.pop()
        for e in E[u]:
            v = e[0]
            if V[v] and V[v] == e[-1] - V[u]:
                pass
            elif V[v]:break
            elif e[-1] > V[u]:
                V[v] = e[-1] - V[u]
                U += [v,]
            else:break
    d += V[0]
print(d)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    par = [None] * (n + 1)
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                par[z] = (x, dat[y/3*3+2])
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        px = []
        pz = []
        x, z = f
        while x != 1:
            px.append(par[x])
            x = par[x][0]
        while z != 1:
            pz.append(par[z])
            z = par[z][0]
        px.reverse()
        pz.reverse()
        while px and pz and px[-1] == pz[-1]:
            px.pop()
            pz.pop()
        px += pz[::-1]
        k = [x[1] for x in px]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(f[1])
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    pu(1)
    dp[1] = 0
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    x = 1 - min(dp[i] for i in xrange(1, n + 1) if col[i] == 1)
    for i in xrange(1, n + 1):
        if col[i] == 1:
            dp[i] += x
        else:
            dp[i] -= x
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 2)
    if x <= 0:
        print 0
    else:
        print x
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import  deque
n, m = list(map(int, input().split()))
node = [list(map(int,input().split())) for _ in range(m)]



nodes =  defaultdict(dict)

for a,b,s in node:
    nodes[a-1][b-1] = s
    nodes[b-1][a-1] = s
a = [None for _ in range(n)]
visited= set([0])

# 0< x
a[0] = (True,1)
x_val  = None
q= deque([0])
while q:
    tmp = q.pop()
    x = a[tmp][0]
    for n_a in nodes[tmp]:
        if n_a in visited:
            if a[n_a][0]==a[tmp][0]:
                #a[n_a][1]+ a[tmp][1]==nodes[tmp][n_a])
                #2x + a[n_a][1]+a[tmp][1] = nodes[tmp][n_a]
                x_val_2 = nodes[tmp][n_a] - (a[n_a][1]+ a[tmp][1])
                if x_val_2 %1 or (x_val is not None and x_val_2//2!=x_val):
                    print(0)
                    #print("31")
                    exit()
                x_val = x_val_2 //2

            if a[n_a][0] !=a[tmp][0] and not   (a[n_a][1]+ a[tmp][1]==nodes[tmp][n_a]):
                #print(36)
                print(0)
                exit()
            continue
        visited.add(n_a)
        a[n_a]= (not x , nodes[tmp][n_a] - a[tmp][1])
        q.append( n_a)


odd_min = 10000000000000
even_min = 1000000000000
for i in range(n):
    if a[i][0]:
        odd_min = min(odd_min,a[i][1])
    else:
        even_min = min(even_min, a[i][1])
#even_min==1
if odd_min>0 and even_min>0:
    if x_val is not None:
        #print("xval")
        print(1)
    else:
        print(even_min)
else:
    print(0)
#print(odd_min,even_min)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import  deque
n, m = list(map(int, input().split()))
node = [list(map(int,input().split())) for _ in range(m)]



nodes =  defaultdict(dict)

for a,b,s in node:
    nodes[a-1][b-1] = s
    nodes[b-1][a-1] = s
a = [None for _ in range(n)]
visited= set([0])

# 0< x
a[0] = (True,1)
x_val  = None
q= deque([0])
while q:
    tmp = q.pop()
    x = a[tmp][0]
    for n_a in nodes[tmp]:
        if n_a in visited:
            if a[n_a][0]==a[tmp][0]:
                #a[n_a][1]+ a[tmp][1]==nodes[tmp][n_a])
                #2x + a[n_a][1]+a[tmp][1] = nodes[tmp][n_a]
                x_val_2 = nodes[tmp][n_a] - (a[n_a][1]+ a[tmp][1])
                if x_val_2 %1 or (x_val is not None and x_val_2//2!=x_val):
                    print(0)
                    #print("31")
                    exit()
                x_val = x_val_2 //2

            if a[n_a][0] !=a[tmp][0] and not   (a[n_a][1]+ a[tmp][1]==nodes[tmp][n_a]):
                #print(36)
                print(0)
                exit()
            continue
        visited.add(n_a)
        a[n_a]= (not x , nodes[tmp][n_a] - a[tmp][1])
        q.append( n_a)


odd_min = 10000000000000
even_min = 1000000000000
for i in range(n):
    if a[i][0]:
        odd_min = min(odd_min,a[i][1])
    else:
        even_min = min(even_min, a[i][1])
#even_min==1
if odd_min>0 and even_min>0:
    if x_val:
        #print("xval")
        print(1)
    else:
        print(even_min)
else:
    print(0)
#print(odd_min,even_min)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        pu(f[1])
        col = [0] * (n + 1)
        col[f[1]] = 1
        par = [None] * (n + 1)
        while st:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if x == f[1] and z == f[0]:
                    s = dat[y/3*3+2]
                elif not col[z]:
                    col[z] = 1
                    par[z] = (x, dat[y/3*3+2])
                    pu(z)
                y = xt[y]
        k = []
        x, z = f
        while x != z:
            k.append(par[x][1])
            x = par[x][0]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(f[1])
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    pu(1)
    dp[1] = 0
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    x = 1 - min(dp[i] for i in xrange(1, n + 1) if col[i] == 1)
    for i in xrange(1, n + 1):
        if col[i] == 1:
            dp[i] += x
        else:
            dp[i] -= x
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 2)
    if x <= 0:
        print 0
    else:
        print x
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        pu(f[1])
        col = [0] * (n + 1)
        col[f[1]] = 1
        par = [None] * (n + 1)
        while st:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if x == f[1] and z == f[0]:
                    s = dat[y/3*3+2]
                elif not col[z]:
                    col[z] = 1
                    par[z] = (x, dat[y/3*3+2])
                    pu(z)
                y = xt[y]
        k = []
        x, z = f
        while x != z:
            k.append(par[x][1])
            x = par[x][0]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(f[1])
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    pu(1)
    dp[1] = 0
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 1) + 1
    for i in xrange(1, n + 1):
        if col[i] == 1:
            dp[i] -= x
        else:
            dp[i] += x
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 2)
    if x <= 0:
        print 0
    else:
        print x
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        pu(f[1])
        col = [0] * (n + 1)
        col[f[1]] = 1
        par = [None] * (n + 1)
        while st:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if x == f[1] and z == f[0]:
                    s = dat[y/3*3+2]
                elif not col[z]:
                    col[z] = 1
                    par[z] = (x, dat[y/3*3+2])
                    pu(z)
                y = xt[y]
        k = []
        x, z = f
        while x != z:
            k.append(par[x][1])
            x = par[x][0]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(f[1])
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    pu(1)
    dp[1] = 0
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 1) + 1
    for i in xrange(1, n + 1):
        if col[i] == 1:
            dp[i] += x
        else:
            dp[i] -= x
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 2)
    if x <= 0:
        print 0
    else:
        print x
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import  deque
n, m = list(map(int, input().split()))
node = [list(map(int,input().split())) for _ in range(m)]



nodes =  defaultdict(dict)

for a,b,s in node:
    nodes[a-1][b-1] = s
    nodes[b-1][a-1] = s
a = [None for _ in range(n)]
visited= set([0])
a[0] = 1
flag_1=False
node_is_odd = [None for _ in range(n)]
node_is_odd[0] = False
q= deque([0])
while q:
    tmp = q.pop()
    this_node_is_odd = node_is_odd[tmp]
    assert this_node_is_odd is not None
    for n_a in nodes[tmp]:
        if n_a in visited:
            if not (a[n_a]+ a[tmp]==nodes[tmp][n_a]):
                print(0)
                exit()
            elif node_is_odd[n_a]==node_is_odd[tmp]:
                flag_1 = True
            continue
        visited.add(n_a)
        node_is_odd[n_a]= not this_node_is_odd
        a[n_a]= nodes[tmp][n_a] - a[tmp]
        q.append(n_a)


odd_min = 10000000000000
even_min = 1000000000000
#print(a)
#print(node_is_odd)
for i in range(n):
    if node_is_odd[i]:
        odd_min = min(odd_min,a[i])
    else:
        even_min = min(even_min, a[i])
#even_min==1
if odd_min>0 and even_min>0:
    if flag_1:
        print(1)
    else:
        print(odd_min)
else:
    print(0)
#print(odd_min,even_min)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import  deque
n, m = list(map(int, input().split()))
node = [list(map(int,input().split())) for _ in range(m)]



nodes =  defaultdict(dict)

for a,b,s in node:
    nodes[a-1][b-1] = s
    nodes[b-1][a-1] = s
a = [None for _ in range(n)]
visited= set([0])
a[0] = 1
node_is_odd = [None for _ in range(n)]
node_is_odd[0] = False
q= deque([0])
while q:
    tmp = q.pop()
    this_node_is_odd = node_is_odd[tmp]
    assert this_node_is_odd is not None
    for n_a in nodes[tmp]:
        if n_a in visited:
            if not (a[n_a]+ a[tmp]==nodes[tmp][n_a]):
                print(0)
                exit()
            continue
        visited.add(n_a)
        node_is_odd[n_a]= not this_node_is_odd
        a[n_a]= nodes[tmp][n_a] - a[tmp]
        q.append(n_a)


odd_min = 10000000000000
even_min = 1000000000000
#print(a)
for i in range(n):
    if node_is_odd[i]:
        odd_min = min(odd_min,a[i])
    else:
        even_min = min(even_min, a[i])
#even_min==1
if odd_min>0 and even_min>0:
    print(odd_min)
else:
    print(0)
#print(odd_min,even_min)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        pu(f[1])
        col = [0] * (n + 1)
        col[f[1]] = 1
        par = [None] * (n + 1)
        while st:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if x == f[1] and z == f[0]:
                    s = dat[y/3*3+2]
                elif not col[z]:
                    col[z] = 1
                    par[z] = (x, dat[y/3*3+2])
                    pu(z)
                y = xt[y]
        k = []
        x, z = f
        while x != z:
            k.append(par[x][1])
            x = par[x][0]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(x)
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    col = [0] * (n + 1)
    pu(1)
    while st:
        x = po()
        if not col[x]:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(z)
                y = xt[y]
        else:
            lo, hi = 1, 1001001001
            col[x] = 2
            y = la[x]
            while y is not None:
                z = dat[y]
                if col[z] == 2:
                    s = dat[y/3*3+2]
                    l, h = s - dp[z][1], s - dp[z][0]
                    if lo < l:
                        lo = l
                    if hi > h:
                        hi = h
                y = xt[y]
            if lo > hi:
                print 0
                return
            dp[x] = (lo, hi)
    ans = dp[1][1] - dp[1][0] + 1
    if ans < 0:
        print 0
        return
    lo = dp[1][0]
    dp = [None] * (n + 1)
    pu(1)
    dp[1] = lo
    while st:
        x = po()
        if dp[x] <= 0:
            print 0
            return
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    print ans
main()

Submission status: Wrong Answer

Solution code:
import queue
n,m=map(int,input().split())
G=[dict() 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
TreeTuple=[(0,0) for i in range(n)]
reached=[0 for i in range(n)]
q=queue.Queue()
q.put(0)
TreeTuple[0]=(0,1)
ZeroCost=-1
IsTree=True
while(not(q.empty())):
    r=q.get()
    reached[r]=1
    for p in G[r]:
        if reached[p]==1:
            continue
        q.put(p)
        tmp=TreeTuple[r]
        tmp2=(G[r][p]-tmp[0],-tmp[1])
        if TreeTuple[p]==(0,0):
            TreeTuple[p]=tmp2
        elif TreeTuple[p]==tmp2:
            nanimosinai=True
        else:
            x=TreeTuple[p][0]-tmp2[0]
            y=tmp2[1]-TreeTuple[p][1]
            if y==0:
                print(0)
                exit()
            elif x%y!=0:
                print(0)
                exit()
            else:
                ZeroCost=x//y
                IsTree=False
                break
    if IsTree==False:
        break
if IsTree:
    L=[]
    R=[0]
    for i in range(n):
        if TreeTuple[i][1]==-1:
            L.append(TreeTuple[i][0]-1)
        else:
            if TreeTuple[i][0]<0:
                R.append(-TreeTuple[i][0]+1)
    print(max([min(L)-max(R),0]))
else:
    P=[0 for i in range(n)]
    q=queue.Queue()
    P[0]=ZeroCost
    q.put(0)
    reached=[0 for i in range(n)]
    while(not(q.empty())):
        r=q.get()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            tmp=G[r][p]-P[r]
            if P[p]==0:
                P[p]=tmp
            elif P[p]==tmp:
                nanimosinai=1
            else:
                print(0)
                exit()
    print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
links={}
for _ in range(m):
    u,v,s=map(int,input().split())
    if u not in links:
        links[u] = [(v,s)]
    else:
        links[u].append((v,s))
    if v not in links:
        links[v]=[(u,s)]
    else:
        links[v].append((u,s))
start=1
queue=deque()
value={}
value[start]=(1,0)
queue.appendleft(start)
oppMinimum=10000000000
#oppMaximum=0
sameMinimum=1
#sameMaximum=0
conflict=False #same parity on the neighbor
while queue:
    v = queue.pop()
    vx,vy=value[v]
    for (w,s) in links[v]:
        if w not in value:
            wx=s-vx
            value[w]=(wx,vy^1)
            if vy==0:
                oppMinimum=min(oppMinimum,wx)
                #oppMaximum=max(oppMaximum,wx)
            else:
                sameMinimum=min(sameMinimum,wx)
                #sameMaximum=max(sameMaximum,wx)
            queue.appendleft(w)
        else:
            wx,wy=value[w]
            if vx+wx !=s:
                if vy^wy==1:
                    print(0)
                    exit()
            if vy==wy:
                conflict=True
                oppMinimum=min(oppMinimum,wx)
                sameMinimum=min(sameMinimum,wx)
ans = oppMinimum + sameMinimum - 1
if ans <=0 :
    print(0)
elif conflict:
    print(1)
else:
    print(ans)
#print([sameMinimum,oppMinimum,ans])

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
links={}
for _ in range(m):
    u,v,s=map(int,input().split())
    if u not in links:
        links[u] = [(v,s)]
    else:
        links[u].append((v,s))
    if v not in links:
        links[v]=[(u,s)]
    else:
        links[v].append((u,s))
start=1
queue=deque()
value={}
value[start]=(1,0)
queue.appendleft(start)
oppMinimum=10000000000
#oppMaximum=0
sameMinimum=1
#sameMaximum=0
conflict=False #same parity on the neighbor
while queue:
    v = queue.pop()
    vx,vy=value[v]
    for (w,s) in links[v]:
        if w not in value:
            wx=s-vx
            value[w]=(wx,vy^1)
            if vy==0:
                oppMinimum=min(oppMinimum,wx)
                #oppMaximum=max(oppMaximum,wx)
            else:
                sameMinimum=min(sameMinimum,wx)
                #sameMaximum=max(sameMaximum,wx)
            queue.appendleft(w)
        else:
            wx,wy=value[w]
            if vx+wx !=s:
                if vy^wy==1:
                    print(0)
                    exit()
                else:
                    conflict=True
            if vy==wy:
                conflict=True
                oppMinimum=min(oppMinimum,wx)
                sameMinimum=min(sameMinimum,wx)
ans = oppMinimum + sameMinimum - 1
if ans <=0 :
    print(0)
elif conflict:
    print(1)
else:
    print(ans)
#print([sameMinimum,oppMinimum,ans])