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:
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)
            else:
                if V[sign][u] != s-val:
                    print(0)
                    exit()

    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)
    print(ans)

main()

Submission status: Accepted

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)
            else:
                if V[sign][u] != s-val:
                    print(0)
                    exit()

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

Solution code:
from collections import deque


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
others = []
UF = UnionFind(n)
for _ in range(m):
    u, v, s = map(int, input().split())
    if not UF.isSameGroup(u, v):
        adj[u].append([v, s])
        adj[v].append([u, s])
        UF.unite(u, v)
    else:
        others.append([u, v, s])

que = deque()
que.append(1)
seen = [0] * (n+1)
seen[1] = 1
val = [0] * (n+1)
plus_min = float('inf')
minus_min = float('inf')
while que:
    v = que.pop()
    for us in adj[v]:
        u, s = us
        if seen[u] == 0:
            que.append(u)
            seen[u] = -seen[v]
            val[u] = s - val[v]
            if seen[u] == -1:
                minus_min = min(minus_min, val[u])
                if minus_min <= 1:
                    print(0)
                    exit()
            else:
                plus_min = min(plus_min, val[u])

x = []
for u, v, s in others:
    if seen[u] != seen[v]:
        if val[u] + val[v] != s:
            print(0)
            exit()
    else:
        if (s - val[u] - val[v]) % 2 == 1:
            print(0)
            exit()
        x_cand = ((s - val[u] - val[v]) // 2) * seen[u]
        if x_cand <= 0:
            print(0)
            exit()
        if plus_min + x_cand <= 0 or minus_min - x_cand <= 0:
            print(0)
            exit()
        if x:
            if x_cand != x[0]:
                print(0)
                exit()
        else:
            x.append(x_cand)

if x:
    print(1)
else:
    if plus_min >= 0:
        print(max(0, minus_min - 1))
    else:
        print(max(0, minus_min - 1 - (-plus_min + 1) + 1))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
UVS = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for u,v,s in UVS:
    u-=1;v-=1
    E[u].append((v,s))
    E[v].append((u,s))

V = [None]*N
V[0] = (0,1)
q = [0]
while q:
    i = q.pop()
    d,n = V[i]
    for j,s in E[i]:
        if V[j] != None: continue
        V[j] = (1-d,s-n)
        q.append(j)

INF = 10**18
checkD = False
checkSum = []
checkMin = [INF]*2
checkMax = [-INF]*2
for i in range(N):
    for j,s in E[i]:
        if j<i: continue
        checkD = checkD or (V[i][0] == V[j][0])
        if V[i][1]+V[j][1]!=s:
            checkSum.append((V[i][0],V[j][0],s-V[i][1]-V[j][1]))
    d = V[i][0]
    checkMin[d] = min(checkMin[d],V[i][1])

if checkD:
    ansFlg = True
    cnt = set()
    for di,dj,s in checkSum:
        if di != dj:
            ansFlg = False
            break
        if di == 1: s *= -1
        cnt.add(s)
    if len(cnt)>1:
        ansFlg = False
    elif cnt:
        d = cnt.pop()
        if d%2: ansFlg = False
        d //= 2
        if min(checkMin[0]+d,checkMin[1]-d) <= 0: ansFlg = False
    ans = int(ansFlg)
else:
    ans = max(sum(checkMin)-1,0)
    if checkSum: ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 全域木上で、解空間は1次式の集まり。

N,M = map(int,input().split())
UVS = [[int(x) for x in input().split()] for _ in range(M)]

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

x = [None] * (N+1) # start = 0, 1として求めた値

x[1] = (0,1)
q = [1]
while q:
    v = q.pop()
    for w,s in graph[v]:
        if x[w] is not None:
            continue
        x[w] = (s-x[v][0],s-x[v][1])
        q.append(w)

# 頂点vの値：x[v][0] + t(x[v][1]-x[v][0])
# tの範囲を絞り込む
INF = 10 ** 18
low, high = -INF,INF

# 頂点が正の整数
for v in range(1,N+1):
    a,b = x[v]
    b -= a
    if b == 1:
        low = max(low, 1-a)
    else:
        high = min(high, a-1)

# 各辺の値が適切
for u,v,s in UVS:
    a,b = x[u][0] + x[v][0], x[u][1] + x[v][1]
    b -= a
    # a + bt == s
    if b == 0:
        if a == s:
            continue
        else:
            high = -INF
            low = INF
            break
    else:
        # 一意に決まる
        q,r = divmod(s-a,b)
        if r != 0:
            high = -INF
            low = INF
            break
        else:
            high = min(high,q)
            low = max(low,q)

answer = high - low + 1
if answer < 0:
    answer = 0
print(answer)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
u, v, s = (
    zip(*(map(int, input().split()) for _ in range(m))) if m else
    ((), (), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


# 適当な全域木をもとに、頂点1に書き込める整数の範囲を求める
# その後、残っている辺について、制約に反することなく整数を書き込めるか判定する
uft = UnionFindTree(n)
E = []
E_ = []
for x, y, w in zip(u, v, s):
    if uft.same(x, y):
        E_.append((x, y, w))
    if not uft.same(x, y):
        E.append((x, y, w))
        uft.union(x, y)

G = [{} for _ in range(n + 1)]
for x, y, w in E:
    G[x][y] = w
    G[y][x] = w
dp = [None for _ in range(n + 1)]
q = [1]
dp[1] = 1
W = {1}
B = set()
while q:
    x = q.pop()
    for y, w in G[x].items():
        if dp[y] is None:
            dp[y] = w - dp[x]
            if x in W:
                B.add(y)
            else:
                W.add(y)
            q.append(y)
W_min = min(dp[x] for x in W)
B_min = min(dp[x] for x in B)

d = -1
for x, y, w in E_:
    if x in W and y in W:
        D = w - dp[x] - dp[y]
        d = (
            D // 2 if D % 2 == 0 and D >= 0 and (d == -1 or D // 2 == d) else
            None
        )
    elif x in B and y in B:
        D = dp[x] + dp[y] - w
        d = (
            D // 2 if D % 2 == 0 and D >= 0 and (d == -1 or D // 2 == d) else
            None
        )
    else:
        d = (
            d if dp[x] + dp[y] == w else
            None
        )
ans = (
    0 if d is None else
    1 if 1 - W_min <= d < B_min else
    max(0, W_min + B_min - 1)
)

print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import setrecursionlimit
from collections import deque
from heapq import heappop, heappush

setrecursionlimit(10**9)
#input = sys.stdin.readline

def inpl(): return map(int, input().split())
INF = 2**31

N, M = inpl()
D = [[] for _ in range(N+1)]

for _ in range(M):
    u, v, s = inpl()
    D[u].append((v, s))
    D[v].append((u, s))

S = [2**31] * (N+1)
C = [-1] * (N+1)
S[1] = 0
C[1] = 0

L = [1] * (N+1)
R = [2**31] * (N+1)

Q = [1]

state = 1
while Q:
    p = Q.pop()
    for q, s in D[p]:
        if C[q] == -1:
            C[q] = int(not C[p])
            S[q] = s - S[p]
            if C[q]:
                R[q] = min(R[q], S[q] - 1)
            else:
                L[q] = max(1, -S[q] + 1)
            Q.append(q)
        elif C[q] == C[p]:
            if C[p] == 0:
                a = s - S[p]
                b = S[q]
            else:
                a = S[q]
                b = s - S[p]

            if (a-b)%2:
                state = 0
                Q = []
                break
            t = (a-b)//2
            if t == L[q] == R[q]:
                continue
            R[q] = t
            L[q] = t
            Q.append(q)


        else:
            if S[q] != s - S[p]:
                state = 0
                Q = []
                break

if state == 0:
    print(0)
elif state == 1:
    print(max(0, min(R) - max(L) + 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
    return sys.stdin.readline()[:-1]
n, m = map(int, input().split())
cyc = [0 for _ in range(n)]
num = [10**30 for _ in range(n)]
adj = [[] for _ in range(n)]
used = [False for _ in range(m)]
for i in range(m):
    u, v, s = map(int, input().split())
    adj[u-1].append([v-1, s, i])
    adj[v-1].append([u-1, s, i])

revised_count = 0 #奇数ループで調整したかどうか
revised = False
novo = -1
vera = -10**30

def dfs(x):
    global revised_count, novo, vera, revised
    for v, s, e in adj[x]:
        #print(x, v, s, e)
        if used[e]:
            #print("hoge0")
            continue
        elif num[v] > 10**20:
            cyc[v] = cyc[x]+1
            num[v] = s-num[x]
            used[e] = True
            dfs(v)
        elif num[v]+num[x] == s:
            used[e] = True
            continue
        elif (cyc[v]-cyc[x])%2 == 1:
            print(0)
            #print("hoge1")
            sys.exit()
        elif revised:
            print(0)
            #print(num)
            #print("hoge2")
            sys.exit()
        elif (s-num[x]+num[v])%2 == 1:
            print(0)
            #print("hoge3")
            #print(s, num[x], num[v])
            sys.exit()
        else:
            novo = v
            vera = (s-num[x]+num[v])//2
            #revised = True
            revised_count += 1
            used[e] = True
    return

num[0] = 0
dfs(0)

if revised_count > 0:
    #print("revised")
    #revised = False
    #revesed_2 = True
    cyc = [0 for _ in range(n)]
    num = [10**30 for _ in range(n)]
    num[novo] = vera
    cyc[novo] = 0
    used = [False for _ in range(m)]
    revised = True
    revised_count = 0
    dfs(novo)
    for i in range(n):
        if num[i] < 0:
            print(0)
            sys.exit()
    print(1)
else:
    even = min([num[i] for i in range(n) if cyc[i]%2 == 0])
    odd = min([num[i] for i in range(n) if cyc[i]%2 == 1])
    print(max(0, even+odd-1))

Submission status: Accepted

Solution code:
from math import ceil,floor
N,M=map(int,input().split())
Graph=[[] for i in range(N)]
for i in range(M):
  a,b,s=map(int,input().split())
  Graph[a-1].append((b-1,s))
  Graph[b-1].append((a-1,s))
inf=float("inf")  
node=[(0,0) for i in range(N)]
visited=[False]*N
node[0],visited[0]=(1,0),True
L,R=1,inf
stack=[0]
while stack:
  n=stack.pop()
  x,y=node[n]
  visited[n]=True
  for i,s in Graph[n]:
    if visited[i]:
      continue
    p,q=node[i]
    stack.append(i)
    if p:
      if p+x==0:
        if y+q!=s:
          print(0)
          exit()
      elif (s-y-q)%(p+x) or (not L<=(s-y-q)/(p+x)<=R):
        print(0)
        exit()
      else:
        L=R=(s-y-q)//(p+x)
    else:
      p,q=-x,s-y
      if p>0:
        L=max(L,floor(-q/p)+1)
      else:
        R=min(R,ceil(-q/p)-1)
      if L>R:
        print(0)
        exit()
      node[i]=(-x,s-y)
print(R-L+1)
#print(node)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**6) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()

INF = float("inf")
graph = [[] for _ in range(n)]

for _ in range(m):
    u,v,s = li()
    u -= 1
    v -= 1
    graph[u].append((v, s))
    graph[v].append((u, s))
    
a = [INF]*n
b = [INF]*n
a[0] = 1
b[0] = 0

def dfs(graph, cur, x):
    for nex, edge in graph[cur]:
        if a[nex] == INF:
            a[nex] = -a[cur]
            b[nex] = edge - b[cur]
            
            res, x = dfs(graph, nex, x)
            
            if not res:
                return False, None
            
        else:
            atemp = -a[cur]
            btemp = edge - b[cur]
            
            if atemp == a[nex]:
                if btemp != b[nex]:
                    return False, None
                
            else:
                if x is not None:
                    if (atemp * x + btemp != a[nex] * x + b[nex])\
                    or (atemp * x + btemp) <= 0:
                        return False, None
                    
                else:
                    if (btemp-b[nex])%(a[nex]-atemp) > 0\
                    or (btemp-b[nex])//(a[nex]-atemp) <= 0:
                        return False, None
                    
                    else:
                        x = (btemp-b[nex])//(a[nex]-atemp)

    return True, x

def find_range(a, b):
    upper = INF
    lower = -INF
    for ai, bi in zip(a,b):
        if ai < 0:
            upper = min(upper, bi)
        else:
            lower = max(lower, -bi)
            
    return max(0, upper-lower-1)

def confirm(a, b, x):
    for ai, bi in zip(a,b):
        if ai*x + bi <= 0:
            return 0
        
    return 1

res, x = dfs(graph, 0, None)

if not res:
    print(0)
    
elif x is not None:
    print(confirm(a,b,x))
    
else:
    print(find_range(a,b))

Submission status: Accepted

Solution code:
import sys
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    table[u-1].append((v-1,s))
    table[v-1].append((u-1,s))
L=[0]*N
T=[1]*N#checker
visit=[False]*N
h=deque()
h.append([0,1])
visit[0]=True
flag=True

K=[]

while h:
    x,t=h.popleft()
    for y,s in table[x]:
        if visit[y]:
            if T[y]==T[x]:
                flag=False
                K.append((x,y,s))
            else:
                if L[y]+L[x]!=s:
                    print(0)
                    sys.exit()
            continue
        T[y]=-t
        visit[y]=True
        L[y]=s-L[x]
        h.append([y,-t])
    
    
if not flag:
    x,y,s=K[0]
    t=T[x]
    u=L[x]+L[y]-s
    if u%2!=0:
        print(0)
        sys.exit()
    u=u//2
    for i in range(N):
        if T[i]==t:
            L[i]-=u
        else:
            L[i]+=u
    for x,y,s in K:
        if L[x]+L[y]!=s:
            print(0)
            sys.exit()
    for i in range(N):
        if L[i]<=0:
            print(0)
            sys.exit()
    print(1)
    sys.exit()
a=10**13
c=10**13
#b=-10**13
#d=-10**13
for i in range(N):
    if T[i]==1:
        a=min(a,L[i])
        #b=max(b,L[i])
    else:
        c=min(c,L[i])
        #d=max(d,L[i])
print(max(0,c+a-1))

Submission status: Accepted

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
        elif visit[y][0]!=inf:
            if (visit[x][0]+visit[y][0])!=d:
                print(0)
                sys.exit()
        if visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
w=(c-t)//2
for i in range(N):
    if visit[i][1]==s:
        x=visit[i][0]
        visit[i]=(x+w,s)
    else:
        x=visit[i][0]
        visit[i]=(x-w,(s+1)%2)
for x,y,d in ans:
    if (visit[x][0]+visit[y][0])!=d:
        print(0)
        sys.exit()
for i in range(N):
    if visit[i][0]<=0:
        print(0)
        sys.exit()
print(1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
N,M=map(int,input().split())
table=[[] for i in range(N)]
ans=[]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1].append((b-1,c))
    table[b-1].append((a-1,c))
    #ans.append((a-1,b-1,c))
h=deque()
inf=-10**13
h.append(0)
flag=True
visit=[(inf,0)]*N
visit[0]=(0,0)
tree=[]
while h:
    #print(h)
    x=h.popleft()
    for y,d in table[x]:
        if visit[y][0]!=inf and visit[y][1]==visit[x][1]:
            flag =False
            tree.append((x,y,d))
        elif visit[y][0]!=inf:
            if (visit[x][0]+visit[y][0])!=d:
                print(0)
                sys.exit()
        elif visit[y][0]==inf:
            t=(visit[x][1]+1)%2
            visit[y]=(d-visit[x][0],t)
            h.append(y)
#print(flag)
#print(visit)
#print(tree)
if flag:
    mi=-inf
    ma=-inf
    for i in range(N):
        if visit[i][1]==0:
            mi=min(mi,visit[i][0])
        else:
            ma=min(ma,visit[i][0])
    print(max(0,ma+mi-1))
    sys.exit()
#print(visit)
a,b,c=tree[0]
s=visit[a][1]
t=visit[a][0]+visit[b][0]
if (c -t)%2==1:
    print(0)
    sys.exit()
w=(c-t)//2
dp=[inf]*N
if s==0:
    dp[0]=w
else:
    dp[0]=-w

k=deque()
k.append(0)
while k:
    x =k.popleft()
    for y,d in table[x]:
        if dp[y]!=inf and (dp[x]+dp[y])!=d:
            print(0)
            sys.exit()
        if dp[y]==inf:
            dp[y]=d-dp[x]
            k.append(y)
for i in range(N):
    if dp[i]<=0:
        print(0)
        sys.exit()
print(1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
p = []
for i in range(m):
    x1,y1,z1,=[int(i) for i in input().split()]
    p.append([x1-1,y1-1,z1])
cost = [[] for i in range(n)]
for path in p:
    cost[path[0]].append((path[1],path[2]))
    cost[path[1]].append((path[0],path[2]))
zan = [[float("inf"),float("inf")] for i in range(n)]
zan[0] = (1,0)
tan =[(0,0)]
e = 0
while len(tan):
  i,j = tan.pop()
  for a,b in cost[i]:
    if (zan[a][0] != float("inf")):
      if abs((j)-zan[a][1]) == 1:
        pass
      elif ((j)-zan[a][1])%2 == 1:
        if zan[a][0] != b - zan[i][0]:
          e=1
          tan = []
          break
      else:
        e = 2
        if zan[a][0] != b - zan[i][0]:
          e = 3
          x = zan[a][0] + zan[i][0]
          if (b-x)% 2 != 0:
            e = 4
            tan = []
            break
          ano = zan[a][0] + (b-x)//2
          ino = zan[i][0] + (b-x)//2
          iti = (j)-zan[a][1]
          zan = [[float("inf"),float("inf")] for i in range(n)]
          zan[a] = (ano,0)
          kime = a
          zan[i] = (ino,iti)
          tan = []
          break
    zan[a] = (b - zan[i][0],j+1)
    tan.append((a,j+1))
  cost[i] = []
if e == 1:
  print(0)
elif e == 2:
  f = 0
  for i in range(n):
    if zan[i][0]<= 0:
      f = 1
      break
  if f == 0:
    print(1)
  else:
    print(0)
elif e == 4:
  print(0)
elif e == 0:
  syou =0
  f = 0
  dai = float("inf")
  for a,b in zan:
    if b %2 ==0:
      if a < 1:
        syou = max(syou,-a+1)
    else:
      if a > 0:
        dai = min(dai,a-1)
      else:
        f = 1
        break
  if f == 1:
    print(0)
  else:
    if dai >= syou:
      print(dai-syou+1)
    else:
      print(0)
elif e == 3:
  tan =[(kime,0)]
  cost = [[] for i in range(n)]
  for path in p:
    cost[path[0]].append((path[1],path[2]))
    cost[path[1]].append((path[0],path[2]))
  while len(tan):
      i,j = tan.pop()
      for a,b in cost[i]:
        if (zan[a][0] != float("inf")):
          if abs((j)-zan[a][1]) == 1:
            pass
          elif ((j)-zan[a][1])%2 == 1:
            if zan[a][0] != b - zan[i][0]:
              e=1
              tan = []
              break
          else:
            if zan[a][0] != b - zan[i][0]:
              e = 1
              break
        zan[a] = (b - zan[i][0],j+1)
        tan.append((a,j+1))
      cost[i] = []
  if e == 1:
    print(0)
  else:
    f = 0
    for i in range(n):
      if zan[i][0]<= 0:
        f = 1
        break
    if f == 0:
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
p = []
for i in range(m):
    x1,y1,z1,=[int(i) for i in input().split()]
    p.append([x1-1,y1-1,z1])
cost = [[] for i in range(n)]
for path in p:
    cost[path[0]].append((path[1],path[2]))
    cost[path[1]].append((path[0],path[2]))
zan = [[float("inf"),float("inf")] for i in range(n)]
zan[0] = (1,0)
tan =[(0,0)]
e = 0
while len(tan):
  i,j = tan.pop()
  for a,b in cost[i]:
    if (zan[a][0] != float("inf")):
      if abs((j)-zan[a][1]) == 1:
        pass
      elif ((j)-zan[a][1])%2 == 1:
        if zan[a][0] != b - zan[i][0]:
          e=1
          tan = []
          break
      else:
        e = 2
        if zan[a][0] != b - zan[i][0]:
          e = 3
          x = zan[a][0] + zan[i][0]
          if (b-x)% 2 != 0:
            e = 4
            tan = []
            break
          ano = zan[a][0] + (b-x)//2
          ino = zan[i][0] + (b-x)//2
          iti = (j)-zan[a][1]
          zan = [[float("inf"),float("inf")] for i in range(n)]
          zan[a] = (ano,0)
          kime = a
          zan[i] = (ino,iti)
          tan = []
          break
    zan[a] = (b - zan[i][0],j+1)
    tan.append((a,j+1))
  cost[i] = []
if e == 1:
  print(0)
elif e == 2:
  f = 0
  for i in range(n):
    if zan[i][0]<= 0:
      f = 1
      break
  if f == 0:
    print(1)
  else:
    print(0)
elif e == 4:
  print(0)
elif e == 0:
  syou =0
  f = 0
  dai = float("inf")
  for a,b in zan:
    if b %2 ==0:
      if a < 1:
        syou = max(syou,-a+1)
    else:
      if a > 0:
        dai = min(dai,a-1)
      else:
        f = 1
        break
  if f == 1:
    print(0)
  else:
    if dai >= syou:
      print(dai-syou+1)
    else:
      print(0)
elif e == 3:
  tan =[(kime,0)]
  cost = [[] for i in range(n)]
  for path in p:
    cost[path[0]].append((path[1],path[2]))
    cost[path[1]].append((path[0],path[2]))
  while len(tan):
      i,j = tan.pop()
      for a,b in cost[i]:
        if (zan[a][0] != float("inf")):
          if abs((j)-zan[a][1]) == 1:
            pass
          elif ((j)-zan[a][1])%2 == 1:
            if zan[a][0] != b - zan[i][0]:
              e=1
              tan = []
              break
          else:
            if zan[a][0] != b - zan[i][0]:
              e = 1
              break
        zan[a] = (b - zan[i][0],j+1)
        tan.append((a,j+1))
      cost[i] = []
  if e == 1:
    print(0)
  else:
    f = 0
    for i in range(n):
      if zan[i][0]<= 0:
        f = 1
        break
    if f == 0:
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

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

maxS = 0
vMaxS = -1
adjL = [[] for v in range(n)]
for i in range(m):
    u, v, s = map(int, input().split())
    adjL[u-1].append((v-1, s))
    adjL[v-1].append((u-1, s))
    if s > maxS:
        maxS = s
        vMaxS = u-1

# sの最大値が2の場合は、全ての頂点に1を書くケースのみが条件を満たす
if maxS == 2:
    print(1)
    exit()

#
def DFS(vNow):
    if len(zRange[vNow]) > 1: return
    zFr, zTo, dz = zRange[vNow][0]
    for v2, s in adjL[vNow]:
        # 頂点vNowの整数範囲と辺の整数sから定まる、頂点v2の整数範囲を条件リストに追加する
        zRange[v2].append((s - zFr, s - zTo, -dz))
        DFS(v2)


zRange = [[] for v in range(n)]
zRange[vMaxS].append((1, maxS-1, 1)) # 頂点vMaxSの整数範囲[1, maxS-1]、1は傾きの意
DFS(vMaxS)


# 各頂点について、課せられた整数範囲条件の共通部分を求める
iRange = [[] for v in range(n)]
for v, zR in enumerate(zRange):
    zR = list(set(zR)) # 重複を排除する
    if len(zR) > 2:
        # 3つ以上の条件が残っている場合、共通部分はない
        print(0)
        exit()
    elif len(zR) == 2:
        s1, ds = zR[0][0], zR[0][2]
        t1, dt = zR[1][0], zR[1][2]
        if ds == dt:
            # 傾きは同じだが範囲が異なる場合、共通部分はない
            print(0)
            exit()
        else:
            # 傾きが異なる場合、交点を求める
            iC = (s1 - t1) / (dt - ds)
            if iC == int(iC) and 0 <= iC <= maxS-2 and s1 + ds * iC > 0:
                iRange[v] = [int(iC), int(iC)]
            else:
                print(0)
                exit()
    else:
        # 条件が1つの場合、「正の整数」である範囲を求める
        s1, ds = zR[0][0], zR[0][2]
        if ds == 1:
            iFr, iTo = max(0, 1-s1), maxS-2
        else:
            iFr, iTo = 0, min(s1-1, maxS-2)

        if iFr <= iTo:
            iRange[v] = [iFr, iTo]
        else:
            print(0)
            exit()

# 全ての頂点の共通範囲をまとめる
iRange = list(zip(*iRange)) # 転置
iFr = max(iRange[0])
iTo = min(iRange[1])
if iFr <= iTo:
    print(iTo - iFr + 1)
else:
    print(0)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

setrecursionlimit(10**6)
n, m = map(int, raw_input().split())
edges = [[] for _ in range(n)]

for i in range(m):
  u, v, s = map(int, raw_input().split())
  u, v = u-1, v-1
  edges[u].append((s, v))
  edges[v].append((s, u))

def quit(x):
  print(x)
  exit()

cond = [[None] * n for _ in range(2)]
cond[0][0] = 0

INF = 10**16

visited = [False] * n

def walk(x):
  if visited[x]:
    return
  visited[x] = True
  for s, y in edges[x]:
    for sig in range(2):
      if cond[sig][x] is not None:
        p = cond[sig][x]
        if cond[1-sig][y] is None or cond[1-sig][y] == s - p:
          cond[1-sig][y] = s - p
        else:
          quit(0)
    walk(y)

walk(0)

for i in range(n):
  if cond[0][i] is not None and cond[1][i] is not None:
    x = (cond[1][i] - cond[0][i]) // 2
    for j in range(n):
      if cond[0][j] is not None and cond[0][j] + x <= 0:
        quit(0)
      if cond[1][j] is not None and cond[1][j] - x <= 0:
        quit(0)
      if cond[0][j] is not None and cond[1][j] is not None and x + cond[0][j] != cond[1][j] - x:
        quit(0)
    quit(1)

pmin = min(p for p in cond[0] if p is not None)
nmin = min(p for p in cond[1] if p is not None)

print(max(0, nmin + pmin - 1))