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: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
G = [[] for _ in range(n)]
for i in range(m):
    u, v, s = LI()
    G[u - 1] += [[v - 1, s]]
    G[v - 1] += [[u - 1, s]]

num = [0] * n
def check(x, r):
    num[x] = r
    qq = [x]
    while qq:
        uii = qq.pop()
        for vii, sii in G[uii]:
            if (num[vii] and sii- num[uii] != num[vii]) or sii - r <= 0:
                return 0
            num[vii] = sii - r
            if num[vii] == 0:
                qq += [vii]
    return 1

flg = [0] * n
M = [0] * n
q = [(0, -1)]
while q:
    ui, pre = q.pop()
    for vi, s in G[ui]:
        if vi == pre:
            continue
        flg[vi] = flg[ui] ^ 1
        M[vi] = s - M[ui]
        if vi == 0:
            if (flg[vi] and M[vi] % 2) or (flg[vi] == 0 and ret):
                print(0)
                exit()
            print(check(vi, M[vi] // 2))
            exit()
        q += [(vi, ui)]
        break

ans = 1
def f(x, pre_x):
    max_i = INF
    min_i = 1
    for vv, ss in G[x]:
        if pre_x == vv:
            continue
        c_min, c_max = f(vv, x)
        max_i = min(max_i, ss - c_min)
        min_i = max(min_i, ss - c_max)
    if min_i > max_i:
        print(0)
        exit()
    return min_i, max_i

a, b = f(0, -1)
print(b - a + 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
G = [[] for _ in range(n)]
for i in range(m):
    u, v, s = LI()
    G[u - 1] += [[v - 1, s]]
    G[v - 1] += [[u - 1, s]]

num = [0] * n
def check(x, r):
    num[x] = r
    qq = [x]
    while qq:
        uii = qq.pop()
        for vii, sii in G[uii]:
            if (num[vii] and sii- num[uii] != num[vii]) or sii - r <= 0:
                return 0
            num[vii] = sii - r
            if num[vii] == 0:
                qq += [vii]
    return 1

ret = 0
flg = [0] * n
min_r = -INF
M = [0] * n
max_r = INF
min_max = [[-INF, INF] for _ in range(n)]
q = [(0, -1)]
while q:
    ui, pre = q.pop()
    for vi, s in G[ui]:
        if vi == pre:
            continue
        flg[vi] = flg[ui] ^ 1
        M[vi] = s - M[ui]
        if vi == 0:
            if (flg[vi] and M[vi] % 2) or (flg[vi] == 0 and ret):
                print(0)
                exit()
            print(check(vi, M[vi] // 2))
            exit()
        q += [(vi, ui)]
        break

ans = 1
def f(x, pre_x):
    max_i = INF
    min_i = 1
    for vv, ss in G[x]:
        if pre_x == vv:
            continue
        c_min, c_max = f(vv, x)
        max_i = min(max_i, ss - c_min)
        min_i = max(min_i, ss - c_max)
    if min_i > max_i:
        print(0)
        exit()
    return min_i, max_i

a, b = f(0, -1)
print(b - a + 1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())

graph=[[] for _ in range(n+1)]
for _ in range(m):
  u,v,s=map(int,input().split())
  graph[u].append((v,s))
  graph[v].append((u,s))
  
def has_cycle(u,par):
  visited[u]=True
  
  ret=False
  for v,w in graph[u]:
    if v==par:
      continue     
    if visited[v]:
      return True
    else:
      if has_cycle(v,u):
        ret=True
      
  return ret

visited=[False]*(n+1)
cyclic=has_cycle(1,0)

min_even=float("inf")
min_odd=float("inf")
def add_score_acyclic(u,par,weight,depth):
  visited[u]=True
  point_list[u]=weight-point_list[par]
  if depth%2==0:
    global min_even
    min_even=min(min_even,point_list[u])
  else:
    global min_odd
    min_odd=min(min_odd,point_list[u])
  
  for v,w in graph[u]:
    if v==par:
      continue     
    add_score_acyclic(v,u,w,depth+1)

if cyclic:
  #temp
  print(1)
else:
  point_list=[0]*(n+1)
  add_score_acyclic(1,0,0,0)
  
  #print(point_list)
  #print(min_even,min_odd)
  print(max(0,min_even+min_odd-1))

Submission status: Runtime Error

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


def is_bipartite(graph):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False
    return True


def color_bipartite(graph):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    return col
             

def make_spanning_tree(graph, root):
    """与えられたグラフから全域木をつくり、二部グラフとして彩色する"""
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    """木のsからtへのパスの頂点を出力する"""
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a, b = a - 1, b - 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

if is_bipartite(graph):
    print(re)
    col = color_bipartite(graph)
    ans = [-1] * n
    ans[0] = 1
    q = deque([0])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, ans[i])
        else:
            min_b = min(min_b, ans[i])
    if min_w < 1:
        min_b += -1 + min_w
        min_w -= -1 + min_w
    print(max(min_b, 0))
    
else:
    col, tree = make_spanning_tree(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
        
    if res % 2 == 1:
        print(0)
        exit()

    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [10 ** 18] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == 10 ** 18:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)

    for a, b, cost in info:
        a, b = a - 1, b - 1
        if ans[a] + ans[b] != cost:
            print(0)
            exit()
    if min(ans) >= 1:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

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


def is_bipartite(graph):
    """二部グラフ判定する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
            elif col[nxt_v] ^ col[v] == 0:
                return False
    return True


def color_bipartite(graph):
    """二部グラフを彩色する"""
    n = len(graph)
    col = [-1] * n
    q = deque([0])
    col[0] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] == -1:
                col[nxt_v] = col[v] ^ 1
                q.append(nxt_v)
    return col
             

def make_spanning_tree(graph, root):
    """与えられたグラフから全域木をつくり、二部グラフとして彩色する"""
    n = len(graph)
    col = [-1] * n
    tree = [set() for i in range(n)]

    q = deque([root])
    col[root] = 0
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if col[nxt_v] != -1:
                continue
            col[nxt_v] = col[v] ^ 1
            tree[v].add(nxt_v)
            tree[nxt_v].add(v)
            q.append(nxt_v)

    return col, tree
  

def trace_path(tree, s, t):
    """木のsからtへのパスの頂点を出力する"""
    n = len(tree)
    dist = [-1] * n
    dist[t] = 0
    q = deque([t])
    while q:        
        v = q.popleft()
        for nxt_v in tree[v]:
            if dist[nxt_v] != -1:
                continue
            dist[nxt_v] = dist[v] + 1 
            q.append(nxt_v)

    trace_path = [s]
    v = s
    while True:
        if dist[v] == 0:
            break
        for nxt_v in tree[v]:
            if dist[nxt_v] + 1 == dist[v]:
                v = nxt_v
                trace_path.append(v)
                break

    return trace_path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
e_cost = {}
for a, b, cost in info:
    a, b = a - 1, b - 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    e_cost[a, b] = cost
    e_cost[b, a] = cost

if is_bipartite(graph):
    col = color_bipartite(graph)
    ans = [-1] * n
    ans[0] = 1
    q = deque([0])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
    min_w = 10 ** 18
    min_b = 10 ** 18
    for i, c in enumerate(col):
        if c == 0:
            min_w = min(min_w, ans[i])
        else:
            min_b = min(min_b, ans[i])
    if min_w < 1:
        min_b += -1 + min_w
        min_w -= -1 + min_w
    print(max(min_b, 0))
    
else:
    col, tree = make_bipartite(graph, 0)
    for v in range(n):
        for nxt_v, _ in graph[v]:
            if nxt_v in tree[v]:
                continue
            if col[v] == col[nxt_v]:
                path = trace_path(tree, v, nxt_v)
                break
        else:
            continue
        break
    res = e_cost[path[0], path[-1]]
    for i in range(len(path) - 1):
        res += e_cost[path[i], path[i + 1]]
    if res % 2 == 1:
        print(0)
        exit()
    res //= 2
    for i in range(len(path) // 2):
        res -= e_cost[path[2 * i], path[2 * i + 1]]

    ans = [-1] * n
    ans[path[-1]] = res
    q = deque([path[-1]])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if ans[nxt_v] == -1:
                ans[nxt_v] = cost - ans[v]
                q.append(nxt_v)
            else:
                if ans[nxt_v] == cost - ans[v]:
                    continue
                else:
                    print(0)
                    exit()
    if min(ans) >= 1:
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
from collections import deque

class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """頂点xを含む集合と頂点y含む集合を結合する"""
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self.cnt -= 1

    def is_same(self, x, y):
        """頂点xと頂点yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

is_tree = True
uf = UnionFind(n)
graph = [[] for i in range(n)]
for i in range(m):
    a, b, cost = info[i]
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    if uf.is_same(a, b):
        is_tree = False
    else:
        uf.merge(a, b)

if is_tree:
    #　木のとき
    root = 0
    val = [0] * n
    val[root] = 33
    visited = [-1] * n
    visited[root] = 0
    q = deque([root])

    ans_minus = []
    ans_plus = [val[root]]
    while q:
        pos = q.pop()
        for next_pos, cost in graph[pos]:
            if visited[next_pos] != -1:
                continue
            visited[next_pos] = visited[pos]^1
            val[next_pos] = cost - val[pos]
            q.append(next_pos)
            if visited[next_pos] == 0:
                  ans_plus.append(val[next_pos])
            else:
                  ans_minus.append(val[next_pos])
    
    max_num = min(ans_plus) - 1
    min_num = -min(ans_minus)
    print(max(0, max_num - min_num))

else:
    # 木でないとき
    print(tmp)

Submission status: Runtime Error

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==0:
        assert False

    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: Runtime Error

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:
        assert False
        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: Runtime Error

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(agkblf)
else:
    print(0)

Submission status: Runtime Error

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 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(agkblf)
else:
    print(0)

Submission status: Runtime Error

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 in G[i]:
            if color[i] == color[j]:
                return False
    return False
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(0)
else:
    print(0)

Submission status: Runtime Error

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 in G[i]:
            if color[i] == color[j]:
                return False
    return False
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(agkblf)
else:
    print(0)

Submission status: Runtime Error

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 in G[i]:
            if color[i] == color[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(agkblf)
else:
    print(0)

Submission status: Runtime Error

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
    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(agkblf)
else:
    print(0)

Submission status: Runtime Error

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(agkblf)
else:
    print(0)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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 color
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: Runtime Error

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(agkbnf)
            print(1)
        else:
            print(fabika)
            print(0)

Submission status: Runtime Error

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(agkbnf)
            print(1)
        else:
            print(0)