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

from heapq import heappush, heappop
x = -1
V = [-1]*n
C = [-1]*n
def bfs0():
    global x
    que = [[0, 0]]
    V[0] = 0
    C[0] = 0 # 0 => x+V[i]; 1 => V[i]-x
    while que:
        co, v = heappop(que)
        if V[v] < co:
            continue
        #print("*", v, V[v])
        k = V[v]
        c = C[v]^1
        for w, s in G[v]:
            if V[w] == -1:
                V[w] = s-k
                C[w] = c
                heappush(que, (s-k, w))
                #print(">", w)
            else:
                #print(v, w, V[w], s, k)
                if C[w] != c:
                    b = s-k
                    if (V[w] + b) % 2 == 1:
                        return 0
                    if C[w]:
                        # V[w]-x = x+b
                        y = (V[w] - b) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
                    else:
                        # V[w]+x = b-x
                        y = (b - V[w]) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
                else:
                    if s-k < V[w]:
                        V[w] = s-k
                        heappush(que, (s-k, w))
    #print(V, C)
    return 1
if not bfs0():
    print(0)
    exit(0)
if x != -1:
    for i in range(n):
        if C[i]:
            if V[i]-x <= 0:
                print(0)
                break
        else:
            if V[i]+x <= 0:
                print(0)
                break
    else:
        print(1)
    exit(0)
mi = 0; ma = 10**30
for i in range(n):
    if C[i]:
        ma = min(ma, V[i])
    else:
        mi = max(mi, -V[i])
print(max(ma-mi-1, 0))

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

from heapq import heappush, heappop
x = -1
V = [-1]*n
C = [-1]*n
def bfs0():
    global x
    que = [[0, 0]]
    V[0] = 0
    C[0] = 0 # 0 => x+V[i]; 1 => V[i]-x
    while que:
        co, v = heappop(que)
        if V[v] < co:
            continue
        #print("*", v, V[v])
        k = V[v]
        c = C[v]^1
        for w, s in G[v]:
            if V[w] == -1:
                V[w] = s-k
                C[w] = c
                heappush(que, (s-k, w))
                #print(">", w)
            else:
                #print(v, w, V[w], s, k)
                if C[w] != c:
                    b = s-k
                    if (V[w] + b) % 2 == 1:
                        return 0
                    if C[w]:
                        # V[w]-x = x+b
                        y = (V[w] - b) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
                    else:
                        # V[w]+x = b-x
                        y = (b - V[w]) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
                else:
                    if s-k < V[w]:
                        V[w] = s-k
                        heappush(que, (s-k, w))
    #print(V, C)
    return 1
if not bfs0():
    print(0)
    exit(0)
if x != -1:
    print(x)
    exit(0)
mi = 0; ma = 10**30
for i in range(n):
    if C[i]:
        ma = min(ma, V[i])
    else:
        mi = max(mi, -V[i])
print(max(ma-mi-1, 0))

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:
                print(0)
                exit()
            if vy==wy:
                conflict=True
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:
n, m = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))

from collections import deque
x = -1
V = [-1]*n
C = [-1]*n
def bfs0():
    global x
    que = deque([0])
    V[0] = 0
    C[0] = 0 # 0 => x+V[i]; 1 => V[i]-x
    while que:
        v = que.popleft()
        #print("*", v, V[v])
        k = V[v]
        c = C[v]^1
        for w, s in G[v]:
            if V[w] == -1:
                V[w] = s-k
                C[w] = c
                que.append(w)
                #print(">", w)
            else:
                #print(v, w, V[w], s, k)
                if C[w] != c:
                    b = s-k
                    if (V[w] + b) % 2 == 1:
                        return 0
                    if C[w]:
                        # V[w]-x = x+b
                        y = (V[w] - b) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
                    else:
                        # V[w]+x = b-x
                        y = (b - V[w]) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
                else:
                    if C[w]:
                        if s-k < V[w]:
                            V[w] = s-k
                            que.append(w)
                    else:
                        if V[w] < s-k:
                            V[w] = s-k
                            que.append(w)
    #print(V, C)
    return 1
if not bfs0():
    print(0)
    exit(0)
if x != -1:
    print(x)
    exit(0)
mi = 0; ma = 10**30
for i in range(n):
    if C[i]:
        ma = min(ma, V[i])
    else:
        mi = max(mi, -V[i])
print(max(ma-mi-1, 0))

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[x] = 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:
        ans = 0
    print ans
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[x] = 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]
            dp[x] = (lo, hi)
    ans = dp[1][1] - dp[1][0] + 1
    if ans < 0:
        ans = 0
    print ans
main()

Submission status: Wrong Answer

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

from collections import deque
x = -1
V = [-1]*n
C = [-1]*n
def bfs0():
    global x
    que = deque([0])
    V[0] = 0
    C[0] = 0 # 0 => x+V[i]; 1 => V[i]-x
    while que:
        v = que.popleft()
        #print("*", v, V[v])
        k = V[v]
        c = C[v]^1
        for w, s in G[v]:
            if V[w] == -1:
                V[w] = s-k
                C[w] = c
                que.append(w)
                #print(">", w)
            else:
                #print(v, w, V[w], s, k)
                if C[w] != c:
                    b = s-k
                    if C[w]:
                        if (V[w] + b) % 2 == 1:
                            return 0
                        # V[w]-x = x+b
                        y = (V[w] - b) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
                    else:
                        # V[w]+x = b-x
                        y = (b - V[w]) // 2
                        if x == -1:
                            if y <= 0:
                                return 0
                            x = y
                        else:
                            if x != y:
                                return 0
    #print(V, C)
    return 1
if not bfs0():
    print(0)
    exit(0)
if x != -1:
    print(x)
    exit(0)
mi = 0; ma = 10**30
for i in range(n):
    if C[i]:
        ma = min(ma, V[i])
    else:
        mi = max(mi, -V[i])
print(max(ma-mi-1, 0))

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[x] = 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]
            dp[x] = (lo, hi)
    ans = dp[1][1] - dp[1][0] + 1
    if ans < 0:
        ans = 0
    print ans
main()

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:
                print(0)
                exit()
            if vy==wy:
                conflict=True
if oppMinimum <= 0:
    print(0)
else:
    ans = oppMinimum + sameMinimum - 1
    if ans <=0 :
        print(0)
    elif conflict:
        print(1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
n, m =  map(int,input().split())
E = [ tuple(map(int,input().split())) for i in range(m)]
d = 0
for i in range(1,E[0][-1]):
    V = ['-' for i in range(n+1)]
    V[:2] = 0, i
    u = 1
    for j in range(1,n+1):
        for e in E:
            if u in e[:2]:
                v = e[1] if e[0]==u else e[0]
                if V[v] == '-':
                    if e[-1] - V[u] > 0:
                        V[v] = e[-1] - V[u]
                        u = v
                elif  V[u] + V[v] == e[-1]:
                    continue
                else:
                    V[0] = 1
                    break
        if V[0]:break
    V[0] = '-' in V
    d += (1-V[0])
print(d)

Submission status: Wrong Answer

Solution code:
# E
from collections import deque

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

case = 1
done_flg = [0]*(n+1)
res_list = [0]*(n+1)
plmi_flg = [0]*(n+1)

queue = deque([1])
done_flg[1] = 1
plmi_flg[1] = 1

dif_list = []

while len(queue) > 0:
    u = queue.popleft()
    for v in G[u].keys():
        if done_flg[v] == 0:
            done_flg[v] = 1
            res_list[v] = G[u][v] - res_list[u]
            plmi_flg[v] = -plmi_flg[u]
            queue.append(v)
        elif plmi_flg[v] == -plmi_flg[u]:
            if res_list[v] != G[u][v] - res_list[u]:
                case = 9
                break
        else:
            d = G[u][v] - res_list[u] - res_list[v]
            if d % 2 == 1:
                case = 9
                break
            else:
                dif_list.append((d // 2)*plmi_flg[u])
                case = 2
            
            
# simple case
if case == 9:
    print(0)
elif case == 2:
    d = dif_list[0]
    check1 = True
    for d_ in dif_list:
        if d_ != dif_list[0]:
            check1 = False
    if check1 == False:
        print(0)
    else:
        for i in range(n+1):
            if plmi_flg[i]==1:
                res_list[i] += d
            elif plmi_flg[i]==-1:
                res_list[i] -= d
        if min(res_list[1:]) > 0:
            print(1)
        else:
            print(0)
elif case == 1:
    res_min_1 = min([res_list[i] for i in range(1, n+1) if plmi_flg[i]==1])
    res_min_2 = min([res_list[i] for i in range(1, n+1) if plmi_flg[i]==-1])
    r = max(0, (res_min_2 - 1) - (-res_min_1 + 1) + 1)
    print(r)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
sys.setrecursionlimit(100000)
# MOD = 10**9 + 7

def solve(f):
    n, m = f.read_int_list()
    g = collections.defaultdict(list)
    g2 = {}
    for _ in xrange(m):
        u, v, s = f.read_int_list()
        g[u].append((v, s))
        g[v].append((u, s))
        g2[(u,v)] = s
        g2[(v,u)] = s

    vis = [None] * (n+1)
    vis[1] = (1, 0)
    res = set()

    def dfs(v):
        for vi, si in g[v]:
            if vis[vi] is not None:
                if v > vi:
                    res.add((vi,v))
                else:
                    res.add((v,vi))
            else:
                vis[vi] = (vis[v][0]*-1, si-vis[v][1])
                dfs(vi)

    dfs(1)

    a = None
    for u, v in res:
        aa = vis[u][0]+vis[v][0]
        if aa == 0:
            if g2[(u,v)] != vis[u][1] + vis[v][1]: return 0
        else:
            bb = g2[(u,v)]-vis[u][1]-vis[v][1]
            a2 = bb / aa
            if aa*a2 != bb: return 0
            if a is not None and a != a2: return 0
            a = a2

    a1min = a2min = float('inf')
    a1max = a2max = -float('inf')
    for i in xrange(1,n+1):
        if vis[i][0] == 1:
            a1min = min(vis[i][1], a1min)
            a1max = max(vis[i][1], a1max)
        else:
            a2min = min(vis[i][1], a2min)
            a2max = max(vis[i][1], a2max)

    # print a1min, a1max, a2min, a2max
    amax = a2min-1
    amin = max(1, -a1min+1)
    # print amax, amin
    if amax < amin:
        return 0
    else:
        if a is not None:
            return max(1, amax-amin+1)
        else:
            return amax-amin+1


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)