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: Accepted

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

ans=[1 for i in range(n)]
pm=[True]*n

used=[False]*n
used[0]=True

que=[0]
while que:
    u=que.pop()
    for v,s in edge[u]:
        if not used[v]:
            pm[v]=(not pm[u])
            ans[v]=s-ans[u]
            used[v]=True
            que.append(v)

flag=True
bipart=True
for u in range(n):
    for v,s in edge[u]:
        if ans[u]+ans[v]!=s:
            flag=False
        if pm[u]==pm[v]:
            bipart=False
            check=(u,v,s)

if bipart:
    upper=float("inf")
    lower=1

    for v in range(1,n):
        if pm[v]:
            lower=max(lower,2-ans[v])
        else:
            upper=min(upper,ans[v])

    if flag:
        if upper<lower:
            print(0)
        else:
            print(upper-lower+1)
    else:
        print(0)
else:
    u,v,s=check
    a,b=ans[u],ans[v]
    if pm[u]:
        diff=s-(ans[u]+ans[v])
        if diff%2==1:
            print(0)
            exit()
        else:
            for i in range(n):
                if pm[i]:
                    ans[i]+=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
                else:
                    ans[i]-=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
            flag=True
            for u in range(n):
                for v,s in edge[u]:
                    if ans[u]+ans[v]!=s:
                        flag=False
            print(int(flag))

    else:
        diff=(ans[u]+ans[v])-s
        if diff%2==1:
            print(0)
            exit()
        else:
            for i in range(n):
                if pm[i]:
                    ans[i]+=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
                else:
                    ans[i]-=diff//2
                    if ans[i]<1:
                        print(0)
                        exit()
            flag=True
            for u in range(n):
                for v,s in edge[u]:
                    if ans[u]+ans[v]!=s:
                        flag=False
            print(int(flag))

Submission status: Accepted

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

def bfs():
    q = deque([0])
    dist = [-1]*n
    dist[0] = 0
    a = [-1]*n
    a[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                a[nv] = w-a[v]
                q.append(nv)
    
    return dist, a
                
n, m = map(int, input().split())
G = [[] for _ in range(n)]
edges = []

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))
    edges.append((u-1, v-1, s))

dist, a = bfs()
ts = set()

for u, v, s in edges:
    if dist[u]%2!=dist[v]%2:
        if a[u]+a[v]!=s:
            print(0)
            exit()
    else:
        if dist[u]%2==0:
            if s-a[u]-a[v]>=2 and (s-a[u]-a[v])%2==0:
                ts.add((s-a[u]-a[v])//2)
            else:
                print(0)
                exit()
        else:
            if a[u]+a[v]-s>=2 and (a[u]+a[v]-s)%2==0:
                ts.add((a[u]+a[v]-s)//2)
            else:
                print(0)
                exit()

if len(ts)>=2:
    print(0)
    exit()

l = 1
r = 10**18
    
for i in range(n):
    if dist[i]%2==0:
        l = max(l, -a[i]+1)
    else:
        r = min(r, a[i]-1)

if len(ts)==1:
    if l<=list(ts)[0]<=r:
        print(1)
    else:
        print(0)
else:
    print(max(0, r-l+1))

Submission status: Accepted

Solution code:
def main():
    ### 初期設定 ###
    n, m = map(int, input().split())
    uvs = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in uvs]
    [g[b-1].append([a-1, c]) for a, b, c in uvs]

    ### 閉路検出 ###
    # やるべきこと
    # DFSで閉路を見つける
    # ・奇閉路が見つかったとき
    # ⇒答えは高々一つなので探索打ち切り。
    # ⇒閉路=[a1,a2,a3,a4,a5]
    # ⇒閉路の辺=[s1,s2,s3,s4,s5]のとき、
    # ⇒a1=((s1+s3+s5)-(s2+s4))//2 に固定される。
    # ・偶閉路が見つかったとき
    # ⇒閉路=[a1,a2,a3,a4,a5,a6]
    # ⇒閉路の辺=[s1,s2,s3,s4,s5,s6]のとき、
    # ⇒S=s1+s3+s5-s2-s4-s6を計算する。
    # ⇒S=0ならば探索を続行する。
    # ⇒S!=0ならば0を出力して強制終了。

    g2 = [{(j, k) for j, k in gg} for gg in g]  # グラフのset化
    q = [0]  # 探索用キュー
    q_dict = {0: 0}  # 頂点がqの中の何番目か
    ac_even = [0]  # 累積和（偶数）
    ac_odd = [0]  # 累積和（奇数）
    flag = False  # 奇閉路があるかどうか
    while q:
        i = q[-1]
        # 行先があった場合
        if g2[i]:
            j, k = g2[i].pop()
            g2[j].remove((i, k))
            # 閉路検出時
            if j in q_dict:
                l = q_dict[j]
                loop_size = len(q)-l
                if len(q) % 2 == 1:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
                # 偶閉路があったとき
                if loop_size % 2 == 0:
                    # ダメな感じの閉路なら終了、それ以外は続行
                    if ac_even[-1]-ac_even[-loop_size//2-1] != ac_odd[-1]-ac_odd[-loop_size//2-1]:
                        print(0)
                        return
                    if len(q) % 2 == 1:
                        ac_even.pop()
                    else:
                        ac_odd.pop()
                # 奇閉路があったとき
                else:
                    flag = True
                    if len(q) % 2 == 1:
                        s = ac_even[-1]-ac_even[-loop_size//2-1] - \
                            ac_odd[-1]+ac_odd[-loop_size//2]
                    else:
                        s = ac_odd[-1]-ac_odd[-loop_size//2-1] - \
                            ac_even[-1]+ac_even[-loop_size//2]
                    if s <= 0 or s % 2 != 0:
                        print(0)
                        return
                    else:
                        ini = [j, s//2]
                        break
            # それ以外
            else:
                q_dict[j] = len(q)
                q.append(j)
                if len(q) % 2 == 0:
                    ac_even.append(ac_even[-1]+k)
                else:
                    ac_odd.append(ac_odd[-1]+k)
        # なかったとき
        else:
            if len(q) % 2 == 0:
                ac_even.pop()
            else:
                ac_odd.pop()
            q.pop()
            q_dict.pop(i)

    ### 探索終了後（奇閉路ありの場合） ###
    # ⇒先程決めた頂点からDFSをスタート。
    # ⇒矛盾が生じたら終了、生じなかったら1を出力。
    g2 = [{(j, k) for j, k in gg} for gg in g]  # グラフのset化
    if flag:
        i, j = ini
        visited = [-1]*n
        visited[i] = j
        q = [i]
        while q:
            i = q[-1]
            j = visited[i]
            if g2[i]:
                k, l = g2[i].pop()
                q.append(k)
                g2[k].remove((i, l))
                new = l-j
                if new <= 0:
                    print(0)
                    return
                if visited[k] == -1:
                    visited[k] = new
                elif visited[k] != new:
                    print(0)
                    return
            else:
                q.pop()
        print(1)
    ### 探索終了後（奇閉路なしの場合） ###
    # ⇒どこかの頂点からDFSをスタート。
    # ⇒各頂点の取りうる値の範囲を1～10**9からスタートさせ、
    # ⇒徐々に狭めていく。
    # ⇒戻る際に過去に通った点にも随時更新をかけていく。
    else:
        visited = [None]*n
        visited[0] = [1, 10**9]
        q = [0]
        s = []
        while q:
            i = q[-1]
            m, M = visited[i]
            if g2[i]:
                j, k = g2[i].pop()
                q.append(j)
                s.append(k)
                g2[j].remove((i, k))
                newM = max(k-m, 0)
                newm = max(k-M, 1)
                if newM == 0:
                    print(0)
                    return
                if visited[j] != None:
                    newM = min(newM, visited[j][1])
                    newm = max(newm, visited[j][0])
                    if newm > newM:
                        print(0)
                        return
                visited[j] = [newm, newM]
            else:
                q.pop()
                if q:
                    j = q[-1]
                    k = s.pop()
                    m, M = visited[i]
                    newM = max(k-m, 0)
                    newm = max(k-M, 1)
                    if newM == 0:
                        print(0)
                        return
                    if visited[j] != None:
                        newM = min(newM, visited[j][1])
                        newm = max(newm, visited[j][0])
                        if newm > newM:
                            print(0)
                            return
                    visited[j] = [newm, newM]
        print(visited[0][1]-visited[0][0]+1)


main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
  e[v].append((u, c))

s = [1]
colour = [0] * (N + 1)
colour[1] = 1
bipartite = 1
while len(s):
  x = s.pop()
  for y, _ in e[x]:
    if colour[y]:
      if colour[y] == colour[x]: bipartite = 0
      continue
    colour[y] = colour[x] % 2 + 1
    s.append(y)
#print(colour, bipartite)
inf = 10 ** 10

def check(x):
  nums = [inf] * (N + 1)
  nums[1] = x
  s = [1]
  while len(s):
    x = s.pop()
    for y, c in e[x]:
      if nums[y] == inf:
        nums[y] = c - nums[x]
        s.append(y)
      elif nums[y] != c - nums[x]:
        return False
  if min(nums) > 0: return True
  else: return False

if bipartite:
  nums = [inf] * (N + 1)
  nums[1] = 1
  s = [1]
  while len(s):
    x = s.pop()
    for y, c in e[x]:
      if nums[y] == inf:
        nums[y] = c - nums[x]
        s.append(y)
  d = 0
  for x in range(2, N + 1):
    if nums[x] > 0: continue
    if colour[x] == 1: d = max(d, 1 - nums[x])
    if colour[x] == 2: d = inf
  if check(1 + d):
    ok = 1 + d
    ng = inf
    while ng - ok > 1:
      m = (ok + ng) // 2
      if check(m): ok = m
      else: ng = m
    print(ok - d)
  else: print(0)
else:
  nums = [inf] * (N + 1)
  nums[1] = 1
  s = [1]
  ps = []
  while len(s):
    x = s.pop()
    for y, c in e[x]:
      if nums[y] == inf:
        nums[y] = c - nums[x]
        s.append(y)
      elif colour[y] == colour[x]:
        ps.append((y, c - nums[x]))
  #print(ps, nums)
  
  y, c = ps[0]
  d = 0
  if colour[y] == 1: d = c - nums[y]
  if colour[y] == 2: d = nums[y] - c

  if d % 2 or (d < 0):
    print(0)
    exit(0)
  if check(1 + d // 2): print(1)
  else: print(0)

Submission status: Accepted

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


def judge(ans):
    """構成した解が正しいかどうか判断"""
    for a, b, cost in info:
        a, b = a - 1, b - 1
        if ans[a] + ans[b] != cost:
            return False
    return True


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
    
    if not judge(ans):
        print(0)
    else:
        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)

    if not judge(ans) or min(ans) <= 0:
        print(0)
    else:
        print(1)

Submission status: Accepted

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)
    for a, b, cost in info:
        a, b = a - 1, b - 1
        if col[a] == col[b]:
            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
    for a, b, cost in info:
        a, b = a - 1, b - 1
        if ans[a] + ans[b] != cost:
            print(0)
            exit()
    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: Accepted

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

n,m=map(int,input().split())

E=[[] for i in range(n+1)]

for i in range(m):
    x,y,s=map(int,input().split())
    E[x].append((y,s))
    E[y].append((x,s))

Q=[1]
USE=[-1]*(n+1)
USE[1]=0
FROM=[-1]*(n+1)

flag=1
while Q and flag==1:
    x=Q.pop()
    #print(x,USE)
    for to,c in E[x]:
        if USE[to]==USE[x]:
            flag=0
            flagpoint=to
            break
        if USE[to]==-1:
            Q.append(to)
            USE[to]=1-USE[x]
            FROM[to]=x

#print(flag,USE)
if flag==0:
    Q=[flagpoint]
    FROM=[-1]*(n+1)
    FROM[flagpoint]=-5
    USE=[-1]*(n+1)
    USE[flagpoint]=0
    flag=1
    while Q and flag==1:
        x=Q.pop()

        for to,c in E[x]:
            if USE[to]==USE[x]:
                flag=0
                break

            if FROM[to]==-1:
                Q.append(to)
                FROM[to]=x
                USE[to]=1-USE[x]

    S1=[to,x]
    while S1[-1]!=flagpoint:
        S1.append((FROM[S1[-1]]))

    S2=[to]
    while S2[-1]!=flagpoint:
        S2.append((FROM[S2[-1]]))

    while S1[-1]==S2[-1]:
        x=S1.pop()
        S2.pop()

    #print(S1,S2)

    ROOP=S1+S2[1:]+[x]
    #print(ROOP)

    score=0
    ind=0

    NOW=ROOP[-1]
    for ind in range(len(ROOP)):
        for to,c in E[ROOP[ind-1]]:
            if to==ROOP[ind]:
                score+=c*(-1)**(ind%2)
                break
        #print(score)
    #print(score)

    if score%2!=0 or score<=0:
        print(0)
        sys.exit()

    ANS=[-1]*(n+1)
        
    ANS[ROOP[-1]]=score//2

    Q=[ROOP[-1]]
    USE=[0]*(n+1)

    while Q:
        x=Q.pop()
        for to,c in E[x]:
            if USE[to]==0:
                USE[to]=1
                ANS[to]=c-ANS[x]
                Q.append(to)

    for i in range(1,n+1):
        if ANS[i]<=0:
            print(0)
            sys.exit()

    flag=1
    for i in range(n+1):
        for to,c in E[i]:
            if ANS[to]+ANS[i]!=c:
                flag=0
                print(0)
                sys.exit()

    print(1)
    sys.exit()

Q=[1]
score=[-1<<31]*(n+1)
score[1]=0
while Q:
    x=Q.pop()
    for to,c in E[x]:
        if score[to]==-1<<31:
            score[to]=c-score[x]
            Q.append(to)
        else:
            if score[to]!=c-score[x]:
                print(0)
                sys.exit()

MIN0=0
MIN1=1<<31

for i in range(1,n+1):
    if USE[i]==0:
        MIN0=min(MIN0,score[i])
    else:
        MIN1=min(MIN1,score[i])

#print(MIN0,MIN1)
print(max(0,max(0,MIN1)+MIN0-1))

Submission status: Accepted

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)]

# import random
#
# N, M = 100, 300
#
# VUS = []
# ns = [random.randint(100, 1000) for _ in range(N)]
# for v, u in generate_undirected_graph(N, M):
#     VUS.append((v, u, ns[v] + ns[u] + 2))

# 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
            if (od - ed) % 2 != 0:
                return 0
            ma = min(ma, (od - ed) // 2)
            mi = max(mi, (od - ed) // 2)
        if od is not None:
            # vまでの距離が奇数のとき
            # 0 < d - s < w
            # d - w < s < d
            ma = min(ma, od - 1)
            mi = max(mi, od - w + 1)
        if 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()
# print(VUS)

Submission status: Accepted

Solution code:
from collections import deque
import sys

n,m = map(int,input().split())

uvs = []
dic = {}

for i in range(m):

    u,v,s = map(int,input().split())
    u -= 1
    v -= 1
    uvs.append([u,v,s])

    if u not in dic:
        dic[u] = []
    if v not in dic:
        dic[v] = []

    dic[u].append([v,s])
    dic[v].append([u,s])


lis = [[0,None] for i in range(n)]

lis[0] = [0,0] #0だと+x
q = deque([0])
flag = False

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        np = i[0]
        nd = i[1]

        if lis[np][1] == None:
            lis[np] = [nd-lis[now][0],lis[now][1]^1]
            q.append(np)

        elif lis[np][1] != lis[now][1]:
            if lis[np][0] != nd - lis[now][0]:
                print (0)
                sys.exit()

        else:

            new = [nd-lis[now][0],lis[now][1]^1]

            if lis[np][1] == 0:
                x = (new[0] - lis[np][0]) // 2
                flag = True
                break
            else:
                x = (lis[np][0] - new[0]) // 2
                flag = True
                break
#print (lis)
if flag: #答えは 0or1

    lis2 = [None] * n
    lis2[0] = x
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()
        for i in dic[now]:

            np = i[0]
            nd = i[1]

            if lis2[np] == None:
                lis2[np] = nd - lis2[now]
                q.append(np)
            elif lis2[np] != nd - lis2[now]:
                print (0)
                sys.exit()

            if min(lis2[now],lis2[np]) <= 0:
                print (0)
                sys.exit()
    #print (lis2)
    print (1)

else: #答えは多様

    m = 1
    M = float("inf")
    #print (lis)

    for i in range(n):

        if lis[i][1] == 0:
            m = max(m , -1 * lis[i][0] + 1)
        else:
            M = min(M , lis[i][0] - 1)

    #print (m,M)
    print (max(0,M-m+1))

Submission status: Accepted

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-D[p]-D[np]) % 2 != 0:
                    ok = False
                    break
                if c == 1:
                    defined_n = (d-D[p]-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: Accepted

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

N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, c = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append((v, c))
    Edge[v].append((u, c))

A = [None]*N
A[0] = (1, 0)
stack = [0]
used = set([0])
inf = 10**20
def f():
    h = None
    while stack:
        vn = stack.pop()
        a, b = A[vn]
        for vf, c in Edge[vn]:
            if vf not in used:
                A[vf] = (-a, c-b)
                stack.append(vf)
                used.add(vf)
            else:
                af, bf = A[vf]
                if a + af == 0:
                    if not b + bf == c:
                        return 0
                elif h is not None:
                    if not (a+af)*h + b + bf == c:
                        return 0
                else:
                    h2 = (c-b-bf)
                    if 1&h2:
                        return 0
                    h = h2//(a+af)
    if h is not None:
        B = [a*h + b for (a, b) in A]
        if all(b > 0 for b in B):
            return 1
        return 0
    else:
        mi = 0
        ma = inf
        for a, b in A:
            if a == 1:
                mi = max(mi, -b)
            if a == -1:
                ma = min(ma, b)
        return max(0, ma-mi-1)
print(f())