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:
import os
import sys

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

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


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

# plot_graph(VUS)

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


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

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


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

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

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


ans = solve()
print(ans)

# test()

Submission status: Wrong Answer

Solution code:
import math
import os
import sys

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

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


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

# plot_graph(VUS)

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


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

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


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

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

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


ans = solve()
print(ans)

# test()

Submission status: Wrong Answer

Solution code:
import os
import sys

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

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

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

# plot_graph(VUS)

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


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

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

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


ans = solve()
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

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

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


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

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


def bipartite(graph):
    stack = [(0, 0)]
    B = [None] * len(graph)
    while stack:
        v, b = stack.pop()
        for u, _ in graph[v]:
            if B[u] is None:
                B[u] = b ^ 1
                stack.append((u, b ^ 1))
            if B[u] != b ^ 1:
                return False
    return True


def dfs(v, n):
    nums = [None] * N
    nums[v] = n
    stack = [(v, n)]
    while stack:
        v, n = stack.pop()
        for u, w in graph[v]:
            if nums[u] == w - nums[v]:
                continue
            if nums[u] is not None and nums[u] != w - nums[v]:
                return u, abs(w - nums[u]), nums[u] - abs(w - nums[u]) // 2
            nums[u] = w - nums[v]
            stack.append((u, nums[u]))
    return v, 0, 0


def dfs2():
    stack = [(0, 0)]
    B = [None] * len(graph)
    while stack:
        v, b = stack.pop()
        for u, _ in graph[v]:
            if B[u] is None:
                B[u] = b ^ 1
                stack.append((u, b ^ 1))
            if B[u] != b ^ 1:
                return False

    v, n = 0, 0
    nums = [None] * N
    nums[v] = n
    stack = [(v, n)]
    while stack:
        v, n = stack.pop()
        for u, w in graph[v]:
            if nums[u] == w - nums[v]:
                continue
            nums[u] = w - nums[v]
            stack.append((u, nums[u]))

    g1 = []
    g2 = []
    for v, n in enumerate(nums):
        [g1, g2][int(B[v])].append(n)
    m1 = min(g1)
    m2 = min(g2)
    if m1 > m2:
        m1, m2 = m2, m1
    m2 += m1 - 1
    m1 -= m1 - 1
    return max(0, m2)


# 二部グラフで矛盾がなければ作れるだけ作れる
# 二部グラフで矛盾があったら0
# 二部グラフじゃなかったら1か0
if bipartite(graph):
    _, diff, _ = dfs(0, 0)
    if diff != 0:
        print(0)
        exit()
    ans = dfs2()
    print(ans)
else:
    v, diff, next_w = dfs(0, 0)
    if diff & 1:
        print(0)
        exit()
    _, diff, _ = dfs(v, next_w)
    if diff == 0:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

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


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))


defined_n = 0
ok = True
even = True
Color = [-1]*N
D = [0]*N
c = 0
q = [0]
Color[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np, d in graph[p]:
            if Color[np] == -1:
                Color[np] = c
                D[np] = d - D[p]
                qq.append(np)
            elif Color[np] != c:
                if (D[p]-d+D[np]) % 2 != 0:
                    ok = False
                    break
                if c == 0:
                    defined_n = (D[p]-d+D[np])//2
                else:
                    defined_n = (D[np]-D[p]+d)//2
                even = False
                break
            elif D[np] != d-D[p]:
                ok = False
                break
        if not ok or not even: break
    if not ok or not even: break
    q = qq

if not ok:
    print(0)
elif not even:
    if defined_n <= 0:
        ok = False
    q = [0]
    score = [-1]*N
    score[0] = defined_n
    while q:
        qq = []
        for p in q:
            s = score[p]
            for np, d in graph[p]:
                if score[np] == -1:
                    if d-s <= 0:
                        ok = False
                        break
                    score[np] = d-s
                    qq.append(np)
                elif score[np] != d-s:
                    ok = False
                    break
            if not ok: break
        if not ok: break
        q = qq
    if not ok:
        print(0)
    else:
        print(1)
else:
    min_n = 0
    max_n = 10**14
    for n in range(N):
        if Color[n] == 0:
            min_n = max(-D[n], min_n)
        else:
            max_n = min(max_n, D[n])
    print(max(0, max_n-min_n-1))

Submission status: Wrong Answer

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


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))


defined_n = 0
ok = True
even = True
Color = [-1]*N
D = [0]*N
c = 0
q = [0]
Color[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np, d in graph[p]:
            if Color[np] == -1:
                Color[np] = c
                D[np] = d - D[p]
                qq.append(np)
            elif Color[np] != c:
                if (D[p]-d+D[np]) % 2 != 0:
                    ok = False
                    break
                if c == 0:
                    defined_n = (D[p]-d+D[np])//2
                else:
                    defined_n = (D[np]-D[p]+d)//2
                even = False
                break
            else:
                D[np] = min(D[np], d-D[p])
        if not ok or not even: break
    if not ok or not even: break
    q = qq

if not ok:
    print(0)
elif not even:
    if defined_n <= 0:
        ok = False
    q = [0]
    score = [-1]*N
    score[0] = defined_n
    while q:
        qq = []
        c ^= 1
        for p in q:
            s = score[p]
            for np, d in graph[p]:
                if score[np] == -1:
                    if d-s <= 0:
                        ok = False
                        break
                    score[np] = d-s
                    qq.append(np)
                elif score[np] != d-s:
                    ok = False
                    break
            if not ok: break
        if not ok: break
        q = qq
    if not ok:
        print(0)
    else:
        print(1)
else:
    min_n = 0
    max_n = 10**14
    for n in range(N):
        if Color[n] == 0:
            min_n = max(-D[n], min_n)
        else:
            max_n = min(max_n, D[n])
    print(max(0, max_n-min_n-1))

Submission status: Wrong Answer

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


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))


defined_n = 0
ok = True
even = True
Color = [-1]*N
D = [0]*N
c = 0
q = [0]
Color[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np, d in graph[p]:
            if Color[np] == -1:
                Color[np] = c
                D[np] = d - D[p]
                qq.append(np)
            elif Color[np] != c:
                if (D[p]-d+D[np]) % 2 == 1:
                    ok = False
                    break
                if c == 0:
                    defined_n = (D[p]-d+D[np])//2
                else:
                    defined_n = (D[np]-D[p]+d)//2
                even = False
            else:
                D[np] = min(D[np], d-D[p])
        if not ok: break
    if not ok: break
    q = qq

if not ok:
    print(0)
elif not even:
    if defined_n <= 0:
        ok = False
    q = [0]
    score = [-1]*N
    score[0] = defined_n
    while q:
        qq = []
        c ^= 1
        for p in q:
            s = score[p]
            for np, d in graph[p]:
                if score[np] == -1:
                    if d-s <= 0:
                        ok = False
                        break
                    score[np] = d-s
                    qq.append(np)
                elif score[np] != d-s:
                    ok = False
                    break
            if not ok: break
        if not ok: break
        q = qq
    if not ok:
        print(0)
    else:
        print(1)
else:
    min_n = 0
    max_n = 10**14
    for n in range(N):
        if Color[n] == 0:
            min_n = max(-D[n], min_n)
        else:
            max_n = min(max_n, D[n])
    print(max(0, max_n-min_n-1))

Submission status: Wrong Answer

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


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))


defined_n = 0
ok = True
even = True
Color = [-1]*N
D = [0]*N
c = 0
q = [0]
Color[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np, d in graph[p]:
            if Color[np] == -1:
                Color[np] = c
                D[np] = d - D[p]
                qq.append(np)
            elif Color[np] != c:
                if (D[p]-d+D[np]) % 2 == 1:
                    ok = False
                    break
                if c == 0:
                    defined_n = (D[p]-d+D[np])//2
                else:
                    defined_n = (D[np]-D[p]+d)//2
                even = False
            elif D[np] != d-D[p]:
                ok = False
                break
            else:
                D[np] = min(D[np], d-D[p])
        if not ok: break
    if not ok:
        break
    q = qq

if not ok:
    print(0)
elif not even:
    if defined_n <= 0:
        ok = False
    q = [0]
    score = [-1]*N
    score[0] = defined_n
    while q:
        qq = []
        c ^= 1
        for p in q:
            s = score[p]
            for np, d in graph[p]:
                if score[np] == -1:
                    if d-s <= 0:
                        ok = False
                        break
                    score[np] = d-s
                    qq.append(np)
                elif score[np] != d-s:
                    ok = False
                    break
            if not ok: break
        if not ok: break
        q = qq
    if not ok:
        print(0)
    else:
        print(1)
else:
    min_n = 0
    max_n = 10**14
    for n in range(N):
        if Color[n] == 0:
            min_n = max(-D[n], min_n)
        else:
            max_n = min(max_n, D[n])
    print(max(0, max_n-min_n-1))

Submission status: Wrong Answer

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


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))


defined_n = 0
ok = True
even = True
Color = [-1]*N
D = [0]*N
c = 0
q = [0]
Color[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np, d in graph[p]:
            if Color[np] == -1:
                Color[np] = c
                D[np] = d - D[p]
                qq.append(np)
            elif Color[np] != c:
                if (D[p]-d+D[np]) % 2 == 1:
                    ok = False
                    break
                if c == 0:
                    tmp_n = (D[p]-d+D[np])//2
                else:
                    tmp_n = (D[np]-D[p]+d)//2
                if not even:
                    if defined_n != tmp_n:
                        ok = False
                        break
                even = False
                defined_n = tmp_n
            elif D[np] != d-D[p]:
                ok = False
                break
            else:
                D[np] = min(D[np], d-D[p])
        if not ok: break
    if not ok:
        break
    q = qq

if not ok:
    print(0)
elif not even:
    if defined_n <= 0:
        ok = False
    c = 0
    q = [0]
    score = [-1]*N
    score[0] = defined_n
    while q:
        qq = []
        c ^= 1
        for p in q:
            s = score[p]
            for np, d in graph[p]:
                if score[np] == -1:
                    if d-s <= 0:
                        ok = False
                        break
                    score[np] = d-s
                    qq.append(np)
                elif score[np] != d-s:
                    ok = False
                    break
            if not ok: break
        if not ok: break
        q = qq
    if not ok:
        print(0)
    else:
        print(1)
else:
    min_n = 0
    max_n = 10**14
    for n in range(N):
        if Color[n] == 0:
            min_n = max(-D[n], min_n)
        else:
            max_n = min(max_n, D[n])
    print(max(0, max_n-min_n-1))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N+1)]
    for u, v, s in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[u].append((v, s))
        E[v].append((u, s))

    V = [[None] * (N+1), [None] * (N+1)]

    def dfs(v=1, sign=1, val=0):
        V[sign][v] = val
        sign = 1 - sign
        for u, s in E[v]:
            if V[sign][u] is None:
                dfs(u, sign, s-val)

    dfs()

    mi, ma = 1, float("inf")
    for m, p in zip(V[0][1:], V[1][1:]):
        if m is not None and p is not None:
            mp = m - p
            if mp % 2 == 0:
                a = mp // 2
                mi = max(mi, a)
                ma = min(ma, a)
            else:
                ma = -1
        if p is not None:
            mi = max(mi, 1-p)
        if m is not None:
            ma = min(ma, m-1)

    ans = max(0, ma-mi+1)

    if ans == 1:
        A = [-1] * (N+1)
        def check(v=1, val=ma):
            A[v] = val
            for u, s in E[v]:
                if A[u] == -1:
                    check(u, s - val)
                else:
                    if A[u] != s - val:
                        print(0)
                        exit()

        check()
        #print(A)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N+1)]
    for u, v, s in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[u].append((v, s))
        E[v].append((u, s))

    V = [[None] * (N+1), [None] * (N+1)]

    def dfs(v=1, sign=1, val=0):
        V[sign][v] = val
        sign = 1 - sign
        for u, s in E[v]:
            if V[sign][u] is None:
                dfs(u, sign, s-val)

    dfs()

    mi, ma = 1, float("inf")
    for m, p in zip(V[0][1:], V[1][1:]):
        if m is not None and p is not None:
            mp = m - p
            if mp % 2 == 0:
                a = mp // 2
                mi = max(mi, a)
                ma = min(ma, a)
            else:
                ma = -1
        if p is not None:
            mi = max(mi, 1-p)
        if m is not None:
            ma = min(ma, m-1)

    print(max(0, ma-mi+1))

main()

Submission status: Wrong Answer

Solution code:
def is_bipartite(G):
    colors = [0]*n
    stack = [(0,1)] # (頂点、色)のタプルをスタックする。最初は(頂点0, 黒(1))
    while stack:
        #スタックから最後に追加された(頂点, 色)をpop
        v,color = stack.pop()
        #今いる点を着色
        colors[v] = color
        #今の頂点から行けるところをチェック
        for to, s in G[v]:
            #同じ色が隣接してしまったらFalse
            if colors[to] == color:
                 return False
            #未着色の頂点があったら反転した色と共にスタックに積む
            if colors[to] == 0:
                 stack.append((to, -color))
    #調べ終わったら矛盾がないのでTrue
    for i in range(n):
        for j, s in G[i]:
            if colors[i] == colors[j]:
                return False
    return True
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
if is_bipartite(G):
    print(100)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def is_bipartite(G):
    v_min = [0, float('inf')]
    value = [-1]*n
    color = [-1]*n
    que = [0]
    color[0] = 0
    value[0] = 0
    while que:
        v = que.pop()
        val = value[v]
        c = color[v]
        for nv, s in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                value[nv] = s-val
                v_min[1-c] = min(v_min[1-c], s-val)
                que.append(nv)
            elif color[nv] == c:
                return (False, v_min, value[nv], s-val, nv)
                
    return (True, v_min, 0, 0, 0)
def C(v, c):
    value = [-1]*n
    que = deque([v])
    value[v] = c
                                                                                
    while que:
        v = que.pop()
        val = value[v]
        for nv, s in G[v]:
            if value[nv]<0:
                value[nv] = s-val
                if s-val<=0:
                    return False          
                que.append(nv)
            elif value[nv] != s-val:
                return False
    return True

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
color = [-1]*n
from collections import deque
flag, v_min, a, b, v = is_bipartite(G)
if flag:
    a, b = v_min
    if a+b<=1:
        print(0)
    else:
        print(a+b-1)
else:
    if (a+b)%2 != 0 or (a+b)<=0:
        print(0)
    else:
        c = (a+b)//2
        if C(v, c):
            print(1)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
def is_bipartite(G):
    n = len(G)
    color = [-1]*n
    que = deque([0])
    color[0] = 0
    while que:
        v = que.pop()
        c = color[v]
        for nv, s in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                que.append(nv)
            elif color[nv] == c:
                return False
    return True
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
if is_bipartite(G):
    print(100)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def is_bipartite(G):
    v_min = [0, float('inf')]
    value = [-1]*n
    color = [-1]*n
    que = deque([0])
    color[0] = 0
    value[0] = 0
    while que:
        v = que.pop()
        val = value[v]
        c = color[v]
        for nv, s in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                value[nv] = s-val
                v_min[1-c] = min(v_min[1-c], s-val)
                que.append(nv)
            elif color[nv] == c:
                return (False, v_min, value[nv], s-val, nv)
    return (True, v_min, 0, 0, 0)
def C(v, c):
    value = [-1]*n
    que = deque([v])
    value[v] = c
                                                                                
    while que:
        v = que.pop()
        val = value[v]
        for nv, s in G[v]:
            if value[nv]<0:
                value[nv] = s-val
                que.append(nv)
            elif value[nv] != s-val:
                return False
    return True

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
color = [-1]*n
from collections import deque
flag, v_min, a, b, v = is_bipartite(G)
if flag:
    a, b = v_min
    if a+b<=1:
        print(0)
    else:
        print(0)
else:
    if (a+b)%2 != 0 or (a+b)<=0:
        print(0)
    else:
        c = (a+b)//2
        if C(v, c):
            print(1)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
def is_bipartite(G):
    v_min = [0, float('inf')]
    value = [-1]*n
    color = [-1]*n
    que = deque([0])
    color[0] = 0
    value[0] = 0
    while que:
        v = que.pop()
        val = value[v]
        c = color[v]
        for nv, s in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                value[nv] = s-val
                v_min[1-c] = min(v_min[1-c], s-val)
                que.append(nv)
            elif color[nv] == c:
                return (False, v_min, value[nv], s-val, nv)
    return (True, v_min, 0, 0, 0)
def C(v, c):
    value = [-1]*n
    que = deque([v])
    value[v] = c
                                                                                
    while que:
        v = que.pop()
        val = value[v]
        for nv, s in G[v]:
            if value[nv]<0:
                value[nv] = s-val
                que.append(nv)
            elif value[nv] != s-val:
                return False
    return True

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
color = [-1]*n
from collections import deque
flag, v_min, a, b, v = is_bipartite(G)
if flag:
    a, b = v_min
    if a+b<=1:
        print(0)
    else:
        print(a+b-1)
else:
    if (a+b)%2 != 0 or (a+b)<=0:
        print(0)
    else:
        c = (a+b)//2
        if C(v, c):
            print(1)
        else:
            print(0)

Submission status: Wrong Answer

Solution code:
def is_bipartite(G):
    v_min = [0, float('inf')]
    value = [-1]*n
    color = [-1]*n
    que = deque([0])
    color[0] = 0
    value[0] = 0
    while que:
        v = que.pop()
        val = value[v]
        c = color[v]
        for nv, s in G[v]:
            if color[nv]<0:
                color[nv] = 1-c
                value[nv] = s-val
                v_min[1-c] = min(v_min[1-c], s-val)
                que.append(nv)
            elif color[nv] == c:
                return (False, v_min, value[nv], s-val, nv)
    return (True, v_min, 0, 0, 0)
def C(v, c):
    value = [-1]*n
    que = deque([v])
    value[v] = c
                                                                                
    while que:
        v = que.pop()
        val = value[v]
        for nv, s in G[v]:
            if value[nv]<0:
                value[nv] = s-val
                if s-val<=0:
                    return False
                que.append(nv)
            elif value[nv] != s-val:
                return False
    return True

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u-1].append((v-1, s))
    G[v-1].append((u-1, s))
color = [-1]*n
from collections import deque
flag, v_min, a, b, v = is_bipartite(G)
if flag:
    a, b = v_min
    if a+b<=1:
        print(0)
    else:
        print(a+b-1)
else:
    if (a+b)%2 != 0 or (a+b)<=0:
        print(0)
    else:
        c = (a+b)//2
        if C(v, c):
            print(1)
        else:
            print(0)