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: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    G[u-1][v-1]=s
    G[v-1][u-1]=s
H=[[] for i in range(N)]
reached=[0 for i in range(N)]
q=[]
q.append(0)
H[0].append((0,1))
while(len(q)>0):
    r=q[-1]
    q.pop()
    reached[r]=1
    for p in G[r]:
        if reached[p]==0:
            q.append(p)
            for s in H[r]:
                H[p].append((G[r][p]-s[0],-s[1]))
flag=0
x=-1
for i in range(N):
    if len(H[i])>=2:
        X=set()
        Y=set()
        for r in H[i]:
            if r[1]==-1:
                X.add(r)
            else:
                Y.add(r)
        if len(X)>=2 or len(Y)>=2:
            print(0)
            exit()
        else:
            a=list(X)[0]
            b=list(Y)[0]
            z=a[0]-b[0]
            if z%2==1:
                print(0)
                exit()
            x=z//2
            if x<0:
                print(0)
                exit()
        flag=1
if flag==1 and x!=-1:
    print(1)
elif flag==1 and x==-1:
    print(0)
else:
    L=[]
    R=[]
    for i in range(N):
        if H[i][0][1]==-1:
            L.append(H[i][0][0])
        else:
            R.append(H[i][0][0])
    print(max([min(L)+min(R)-1,0]))

Submission status: Time Limit Exceeded

Solution code:
import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    G[u-1][v-1]=s
    G[v-1][u-1]=s
H=[[] for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
q.put(0)
H[0].append((0,1))
while(not(q.empty())):
    r=q.get()
    reached[r]=1
    for p in G[r]:
        if reached[p]==0:
            q.put(p)
            for s in H[r]:
                H[p].append((G[r][p]-s[0],-s[1]))
flag=0
x=-1
for i in range(N):
    if len(H[i])>=2:
        X=set()
        Y=set()
        for r in H[i]:
            if r[1]==-1:
                X.add(r)
            else:
                Y.add(r)
        if len(X)>=2 or len(Y)>=2:
            print(0)
            exit()
        else:
            a=list(X)[0]
            b=list(Y)[0]
            z=a[0]-b[0]
            if z%2==1:
                print(0)
                exit()
            x=z//2
            if x<0:
                print(0)
                exit()
        flag=1
if flag==1 and x!=-1:
    print(1)
elif flag==1 and x==-1:
    print(0)
else:
    L=[]
    R=[]
    for i in range(N):
        if H[i][0][1]==-1:
            L.append(H[i][0][0])
        else:
            R.append(H[i][0][0])
    print(max([min(L)+min(R)-1,0]))

Submission status: Time Limit Exceeded

Solution code:
import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    G[u-1][v-1]=s
    G[v-1][u-1]=s
H=[[] for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
for i in range(N):
    if reached[i]==0:
        q.put(i)
        H[i].append((0,1))
        while(not(q.empty())):
            r=q.get()
            reached[r]=1
            for p in G[r]:
                if reached[p]==0:
                    q.put(p)
                    for s in H[r]:
                        H[p].append((G[r][p]-s[0],-s[1]))
flag=0
x=-1
for i in range(N):
    if len(H[i])>=2:
        X=set()
        Y=set()
        for r in H[i]:
            if r[1]==-1:
                X.add(r)
            else:
                Y.add(r)
        if len(X)>=2 or len(Y)>=2:
            print(0)
            exit()
        else:
            a=list(X)[0]
            b=list(Y)[0]
            z=a[0]-b[0]
            if z%2==1:
                print(0)
                exit()
            x=z//2
            if x<0:
                print(0)
                exit()
        flag=1
if flag==1 and x!=-1:
    print(1)
elif flag==1 and x==-1:
    print(0)
else:
    L=[]
    R=[]
    for i in range(N):
        if H[i][0][1]==-1:
            L.append(H[i][0][0])
        else:
            R.append(H[i][0][0])
    print(max([min(L)+min(R)-1,0]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import combinations

inf = float('inf')

n, m =  map(int,input().split())
E = defaultdict(set)
for i in range(m):
    u,v,s = map(int,input().split())
    E[u].add((v,s))
    E[v].add((u,s))

E1 = defaultdict(set)
for u in range(1,n+1):
    for (v,s1), (w,s2) in combinations(E[u], 2):
        E1[v].add((w,s2-s1))
        E1[w].add((v,s1-s2))

db=defaultdict(lambda:inf)
db[1] = 0
dt = defaultdict(lambda:inf)
for v, s in E[1]:
    dt[v] = s
dt[1] = inf

for _ in [0]*n:
    for u in range(1, n+1):
        for v,c in E1[u]:
            eb = db[u] + c
            if eb<db[v]:db[v] = eb
            et = dt[u] + c
            if et<dt[v]:dt[v] = et

b = min(db.values())
t = min(dt.values())

print(max(0, t+b-1))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
from itertools import combinations

inf = float('inf')
def bellman_ford(n,E,s=1,d=defaultdict(lambda:inf),init=0):
    d[s] = init
    for _ in [0]*n:
        for u in range(1, n+1):
            for v,c in E[u]:
                e = d[u] + c
                if e<d[v]:d[v] = e
    return d

n, m =  map(int,input().split())
E = defaultdict(set)
for i in range(m):
    u,v,s = map(int,input().split())
    E[u].add((v,s))
    E[v].add((u,s))

E1 = defaultdict(set)
for u in range(1,n+1):
    for (v,s1), (w,s2) in combinations(E[u], 2):
        E1[v].add((w,s2-s1))
        E1[w].add((v,s1-s2))
b = min(bellman_ford(n,E1,init=0).values())

d = defaultdict(lambda:float('inf'))
for v, s in E[1]:
    d[v] = s
t = min(bellman_ford(n,E1,d=d,init=inf).values())

print(max(0, t+b-1))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
from itertools import permutations

inf = float('inf')
def bellman_ford(n,E,s=1,d=defaultdict(lambda:inf),init=0):
    d[s] = init
    for _ in [0]*n:
        for u in range(1, n+1):
            for v,c in E[u]:
                e = d[u] + c
                if e<d[v]:d[v] = e
    return d

n, m =  map(int,input().split())
E = defaultdict(set)
for i in range(m):
    u,v,s = map(int,input().split())
    E[u].add((v,s))
    E[v].add((u,s))

E1 = defaultdict(set)
for u in range(1,n+1):
    for (v,s1), (w,s2) in permutations(E[u], 2):
        E1[v].add((w,s2-s1))
        E1[w].add((v,s1-s2))
d = bellman_ford(n,E1,init=0)
b = -min(d.values())

d=defaultdict(lambda:float('inf'))
for v, s in E[1]:d[v] = s
d = bellman_ford(n,E1,d=d,init=inf)
t = min(d.values())

print(max(0,t-b-1))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
from itertools import permutations

inf = float('inf')
def bellman_ford(n,E,s=1,d=defaultdict(lambda:inf),p=defaultdict(lambda:-1),init=0,compare=lambda a,b:a<b):
    d[s] = init
    hq = [(init,s)]
    for i in range(1, n+1):
        for u in range(1, n+1):
            for v,c in E[u]:
                e = d[u] + c
                if compare(e,d[v]):
                    d[v] = e
                    p[v] = u
                if i==n:
                    'negcy'
    return d, p

n, m =  map(int,input().split())
u0, s0, d = 0, 0, 0

E = defaultdict(set)
for i in range(m):
    u,v,s = map(int,input().split())
    E[u].add((v,s))
    E[v].add((u,s))
    if s0 < 1 or s0 > s:
        u0,s0 = u,s

E1 = defaultdict(set)
for u in range(1,n+1):
    for (v,s1), (w,s2) in permutations(E[u], 2):
            E1[v].add((w,s1-s2))
            E1[w].add((v,s2-s1))
d,p = bellman_ford(n,E1,s=u0,d=defaultdict(lambda:-inf),p=defaultdict(lambda:-1),init=0,compare=lambda a,b:a>b)
b = max(d.values())

E2 = defaultdict(set)
for u in range(1,n+1):
    for (v,s1), (w,s2) in permutations(E[u], 2):
            E2[v].add((w,-s1+s2))
            E2[w].add((v,-s2+s1))
d=defaultdict(lambda:float('inf'))
for v, s in E[u0]:
    d[v] = s
d,p = bellman_ford(n,E2,s=u0,d=d,p=defaultdict(lambda:-1),init=inf,compare=lambda a,b:a<b)
t = min(d.values())
print(max(0,t-b-1))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, raw_input().split())
edges = [[] for _ in range(n)]

nums = []
for i in range(m):
  nums.append(map(int, raw_input().split()))
nums.sort(key=lambda x: x[2])
start_u = nums[0][0] - 1
max_i = nums[0][2] - 1

for item in nums:
  u, v, s = item
  u, v = u-1, v-1
  edges[u].append([v, s])
  edges[v].append([u, s])
i = 1
total = 0

while i <= max_i:
  values = [0] * n
  values[start_u] = i
  q = [[start_u] + t for t in edges[start_u]]
  visited = [False] * n
  visited[start_u] = True
  legal = True
  while q and legal:
    from_to, to_next, vs = q.pop()
    visited[to_next] = True
    if values[to_next] == 0:
      values[to_next] = vs - values[from_to]
      if values[to_next] <= 0:
        legal = False
      else:
        for item in edges[to_next]:
          if visited[item[0]] == False:
            q.append([to_next, item[0], item[1]])
    elif values[to_next] == vs - values[from_to]:
      for item in edges[to_next]:
          if visited[item[0]] == False:
            q.append([to_next, item[0], item[1]])
    else:
      legal = False
  i += 1
  if legal:
    total += 1
  else:
    if total > 0:
      break
print(total)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m =  map(int,input().split())
E = np.array([list(map(int,input().split())) for i in range(m)])
e0 = E[:, -1].argmin()
d = 0
for i in range(1,E[e0,-1]):
    V = np.array([0 for i in range(n+1)])
    V[0] = 1
    V[E[e0, 0]] = i
    U = [E[e0, 0],]
    while U and V[0]:
        u = U.pop()
        for j in (0,1):
            for e in E[np.where(E[:,j]==u)]:
                v = e[1-j]
                if V[v] and V[v] == e[-1] - V[u]:
                    continue
                elif V[v]:
                    V[0] = 0
                    break
                elif e[-1] - V[u] > 0:
                    V[v] = e[-1] - V[u]
                    U.append(v)
                else:
                    V[0] = 0
                    break
        if not V[0]: break
    d += V[0]
print(d)

Submission status: Time Limit Exceeded

Solution code:
n, m =  map(int,input().split())
import numpy as np
E = np.array([ list(map(int,input().split())) for i in range(m)])
e0 = E[:, -1].argmin()
d = 0
for i in range(1,E[e0,-1]):
    V = np.array([[0 for i in range(n+1)], [0 for i in range(n+1)]])
    V[:,0] = 1
    V[0,E[e0, 0]] = i
    while V[1].min()==0 and V[0,0]:
        u = np.where((V[0] != 0) & (V[1] == 0))[0][0]
        for j in (0,1):
            for e in E[np.where(E[:,j]==u)]:
                v = e[1-j]
                if V[0,v] and V[0,v] == e[-1] - V[0,u]:
                    continue
                elif V[0,v]:
                    V[0,0] = 0
                    break
                elif e[-1] - V[0,u] > 0:
                    V[0,v] = e[-1] - V[0,u]
                else:
                    V[0,0] = 0
                    break
        V[1,u] = 1
        if not V[0,0]: break
    d += V[0,0]
print(d)

Submission status: Time Limit Exceeded

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

u = [0 for _ in range(m)]
v = [0 for _ in range(m)]
s = [0 for _ in range(m)]

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

p = [0 for _ in range(n + 1)]

def search_path(f, g):
  check = 0
  for i in range(m):
    if u[i] == f:
      if p[v[i]] == 0:
        check = 1
        temp = s[i] - g
        if temp > 0:
          p[v[i]] = temp
          if search_path(v[i], temp) == 1:
            return 1
        else:
          return 1
      elif p[v[i]] != s[i] - g:
        return 1
    if v[i] == f:
      if p[u[i]] == 0:
        check = 1
        temp = s[i] - g
        p[u[i]] = temp
        if search_path(u[i], temp) == 1:
          return 1
      elif p[u[i]] != s[i] - g:
        return 1
  return 0

result = 0
for i in range(1, s[0]):
  p = [0 for _ in range(n + 1)]
  p[u[0]] = i
  check = 1
  if search_path(u[0], i) == 0:
    for j in range(m):
      if p[u[j]] + p[v[j]] != s[j]:
        check = 0
        break
    result += check

print(result)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
e=[[]for _ in[0]*-~n]
uvs=[list(map(int,input().split()))for _ in[0]*m]
u0,v0,s0=min(uvs,key=lambda x:x[2])
for u,v,s in uvs:
    e[u]+=[(v,s)]
    e[v]+=[(u,s)]
ans=0
for i in range(1,s0):
    p=[1]+[0]*n
    p[u0],p[v0]=i,s0-i
    flag=True
    for v,s in e[u0]:
        p[v]=s-p[u0]
        if p[v]<=0:
            flag=False
            break
    if not flag:
        continue
    for v,s in e[v0]:
        if p[v]:
            if p[v]+p[v0]!=s:
                flag=False
                break
        else:
            p[v]=s-p[v0]
            if p[v]<=0:
                flag=False
                break
    if not flag:
        continue
    while 0 in p and flag:
        u=p.index(0)
        for v,s in e[u]:
            if p[v]:
                p[u]=s-p[v]
                if p[u]<=0:
                    flag=False
                break
    if not flag:
        continue
    for u in range(1,n+1):
        if not flag:
            break
        for v,s in e[u]:
            if p[u]+p[v]!=s:
                flag=False
                break
    ans+=flag
print(ans)

Submission status: Accepted

Solution code:
#(x,y)...xt+yが書かれる
from collections import deque
N,M=map(int,input().split())
G=[{} for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    u-=1;v-=1
    G[u][v]=s;G[v][u]=s
H=[(0,0) for i in range(N)]
t=None
q=deque([0])
H[0]=(1,0)
while(q):
    r=q.pop()
    for p in G[r]:
        s=G[r][p]
        tmp=(-H[r][0],s-H[r][1])
        if H[p]==(0,0):
            H[p]=tmp
            q.append(p)
        elif H[p]==tmp:
            pass
        else:
            if H[p][0]==tmp[0]:
                print(0)
                exit()
            else:
                a=H[p][1]
                b=tmp[1]
                if H[p][0]==-1:
                    a,b=b,a
                #t+a=-t+b
                #2t=b-a
                if (b-a)%2:
                    print(0)
                    exit()
                else:
                    t=(b-a)//2
'''
t+a>=0:t>=-a
-t+b>=0:t<=b
inf=max(a)
sup=min(b)
'''
if t==None:
    inf=0
    sup=10**18
    for i in range(N):
        if H[i][0]==1:
            inf=max(inf,-H[i][1])
        else:
            sup=min(sup,H[i][1])
    print(max(sup-inf-1,0))
else:
    ans=[None for i in range(N)]
    q=deque([0])
    ans[0]=t
    while(q):
        r=q.pop()
        for p in G[r]:
            if ans[p]==None:
                ans[p]=G[r][p]-ans[r]
                q.append(p)
    flag=1
    for i in range(N):
        for j in G[i]:
            if ans[i]+ans[j]!=G[i][j]:
                flag=0
                break
        if flag==0:
            break
    if flag and min(ans)>0:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
# 【条件1】各ノードに記載する数字が全部正の整数
# start: v (> 0) として
# 1: s1 - v > 0            =>  s1 > v
# 2: s2 - s1 + v > 0       =>  v > s1 - s2
# 3: s3 - s2 + s1 - v > 0  =>  s1 - s2 + s3 > v
# 4: ...
# -> max{0, s1 - s2, s1 - s2 + s3 - s4, ...} < v < min{s1, s1 - s2 + s3, ...}
#    なので、max{0, 右辺 - 左辺 - 1} が答え。
# 【条件2】 loopがあったらそのloop上で s1 - s2 + s3 - s4 + ... = 0 じゃないとダメ
# あるノードまで複数の行き方で行けた場合、
# 偶奇が同じケースなら
#   s1 - s2 + s3 - ... = s'1 - s'2 + s'3 - ...
# が成り立っていれば整合性は保たれる。
# 偶奇が異なるケースなら、
# v = (奇のs + 遇のs) / 2
# の時のみ整合性が保たれる。
from collections import defaultdict, deque


def main():
    INF = 10 ** 15
    N, M = map(int, input().split())
    S = defaultdict(int)
    adj = defaultdict(list)
    for _ in range(M):
        u, v, s = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
        S[(u, v)], S[(v, u)] = s, s
    even_sum_s, odd_sum_s = [- INF] * N, [INF] * N
    start = 0
    even_sum_s[start] = 0
    que = deque([(start, -1, 0, 0)])  # (node, parent, dist from start, sum of signed `s`)
    unique_n = -1
    # DFS
    while len(que) > 0:
        node, parent_node, dist, sum_s = que.pop()
        for next_node in adj[node]:
            if parent_node == next_node:
                continue
            next_dist = dist + 1
            if next_dist % 2 == 1:
                next_sum_s = sum_s + S[(node, next_node)]
                if even_sum_s[next_node] != - INF:
                    s = next_sum_s + even_sum_s[next_node]
                    if s < 2 or s % 2 != 0 or (unique_n > 0 and unique_n != s // 2):
                        print(0)
                        return
                    unique_n = s // 2
                if odd_sum_s[next_node] == INF:
                    odd_sum_s[next_node] = next_sum_s
                    que.append((next_node, node, next_dist, next_sum_s))
                else:
                    if odd_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
            else:
                next_sum_s = sum_s - S[(node, next_node)]
                if odd_sum_s[next_node] != INF:
                    s = odd_sum_s[next_node] + next_sum_s
                    if s < 2 or s % 2 != 0 or (unique_n > 0 and unique_n != s // 2):
                        print(0)
                        return
                    unique_n = s // 2
                if even_sum_s[next_node] == - INF:
                    even_sum_s[next_node] = next_sum_s
                    que.append((next_node, node, next_dist, next_sum_s))
                else:
                    if even_sum_s[next_node] != next_sum_s:
                        print(0)
                        return
    lower, upper = max(even_sum_s), min(odd_sum_s)
    if unique_n > 0:
        if lower < unique_n < upper:
            print(1)
        else:
            print(0)
    else:
        print(max(0, upper - lower - 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        u,v,s=MI()
        u-=1
        v-=1
        adj[u].append((v,s))
        adj[v].append((u,s))
    
    #　頂点0を根として，ここの値aとする，各頂点Xa+Cの形で表して，最大値と最小値の候補を絞っていく．ループがあるかをしっかり判断
    
    # Xはaの係数，1orー１が入る．0ならまだ見ていない
    X=[0]*N
    C=[0]*N
    
    X[0]=1
    
    floor=1
    ceil=10**9
    
    import queue
    q=queue.Queue()
    q.put((0,-1))#v,p
    
    while not q.empty():
        v,p=q.get()
        
        
        for nv,s in adj[v]:
            if nv!=p:
                nx=X[v]*(-1)
                nc=s-C[v]
                
                #見巡回の頂点なら
                if X[nv]==0 and C[nv]==0:
                    q.put((nv,v))
                    X[nv]=nx
                    C[nv]=nc
                    
                    # aの係数が正ならば，下限を更新
                    if nx==1:
                        floor=max(floor,-1*nc+1)
                        
                    #aの係数が負ならば上限を更新
                    else:
                        ceil=min(ceil,nc-1)
                        
                else:
                    # 既存のものと変わらなければ何もしない
                    if nx==X[nv] and nc==C[nv]:
                        pass
                    #係数が同じで定数部分が違えば無理
                    elif nx==X[nv]:
                        ceil=-1
                    #係数が違う場合，一意に決まる
                    else:
                        ac=0#係数が正の方の定数
                        bc=0#係数が負の方の定数
                        if nx==1:
                            ac=nc
                            bc=C[nv]
                        else:
                            ac=C[nv]
                            bc=nc
                        
                        # 2*aの値
                        aa=bc-ac
                        
                        if aa<=0 or aa%2==1:
                            ceil=-1
                        else:
                            ceil=ceil=min(ceil,aa//2)
                            floor=max(floor,aa//2)
                # print(nv,floor,ceil)
                            
    ans=ceil-floor+1
    if ans<=0:
        ans=0
    print(ans)
    
    
                            

                        
    

main()

Submission status: Accepted

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

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, s = map(int, input().split())
    G[u].append((v, s))
    G[v].append((u, s))
val = [None] * (n+1)
val[1] = (1, 0)
queue = deque([1])
while queue:
    u = queue.popleft()
    for v, s in G[u]:
        if val[v]:
            continue
        val[v] = (-val[u][0], s - val[u][1])
        queue.append(v)
ma = float('inf')
mi = 1
x = -1
for u in range(1, n+1):
    if val[u][0] == -1:
        ma = min(ma, val[u][1] - 1)
    else:
        mi = max(mi, -val[u][1] + 1)
    for v, s in G[u]:
        if u > v:
            continue
        if val[u][0] + val[v][0] == 0:
            if val[u][1] + val[v][1] != s:
                print(0)
                exit()
        else:
            a = val[u][0] + val[v][0]
            b = s - (val[u][1] + val[v][1])
            if a < 0:
                b *= -1
            if b <= 0 or b % 2 == 1:
                print(0)
                exit()
            if x == -1:
                x = b // 2
            elif x != b // 2:
                print(0)
                exit()
if x != -1:
    if mi <= x <= ma:
        print(1)
    else:
        print(0)
else:
    print(max(ma - mi + 1, 0))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int, readline().split())
uvs = list(map(int,read().split()))

links = [dict() for _ in range(n+1)]
it = iter(uvs)
for u,v,s in zip(it,it,it):
    links[u][v] = s
    links[v][u] = s

def dfs(root, init):
    nums = [0] * (n+1)
    depth = [-1] * (n+1)
    parent = [-1] * (n+1)

    nums[root] = init
    depth[root] = 0
    stack = [root]
    while(stack):
        next = []
        while(stack):
            i = stack.pop()
            for j,s_ij in links[i].items():
                if(j == parent[i]):
                    continue

                num_j = s_ij - nums[i]
                if(depth[j] != -1)&(nums[j] != num_j):
                    loop_len = depth[j] + depth[i] + 1
                    if(loop_len%2 == 0):
                        print(0)
                        exit()
                    else:
                        num_j = nums[j] + num_j
                        if(num_j % 2 ==1):
                            print(0)
                            exit()
                        return (False, nums,depth,j,num_j//2)
                elif(depth[j] == -1):
                    depth[j] = depth[i] + 1
                    nums[j] = num_j
                    parent[j] = i
                    next.append(j)
        stack = next[::]

    return(True, nums,depth,0,0)

flag,nums,depth,root,init = dfs(1,0)

if(flag==False):
    flag2,nums,depth,root,init = dfs(root,init)
    if(flag2==False):
        print(0)
    else:
        if(min(nums[1:]) < 1):
            print(0)
        else:
            print(1)
    exit()

even = []
odd = []
for i in range(1,n+1):
    if(depth[i]%2==0):
        even.append(nums[i])
    else:
        odd.append(nums[i])

min0 = min(even)
min1 = min(odd)

ans = 1 + (min0-1) + (min1-1)
print(max(0,ans))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    g = False
    way = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,s = map(int,ipt().split())
        way[u].append((v,s))
        way[v].append((u,s))
    ans = [10**18]*(n+1)
    par = [0]*(n+1)
    ans[1] = 1
    q = [1]
    par[1] = 1
    while q:
        qi = q.pop()
        pqi = par[qi]
        aqi = ans[qi]
        for i,si in way[qi]:
            if ans[i] == 10**18:
                q.append(i)
                ans[i] = si-aqi
                par[i] = pqi*(-1)
            elif par[i] == pqi:
                g = True
                a = ans[i]+si-aqi
                if a&1:
                    print(0)
                    exit()
                stt = i
                sa = a//2
                if sa <= 0:
                    print(0)
                    exit()
                break
            elif ans[i] != si-aqi:
                print(0)
                exit()
        if g:
            break
    if g:
        ans = [10**18]*(n+1)
        ans[stt] = sa
        q = [stt]
        while q:
            qi = q.pop()
            aqi = ans[qi]
            for i,si in way[qi]:
                if ans[i] == 10**18:
                    if si-aqi <= 0:
                        print(0)
                        exit()
                    q.append(i)
                    ans[i] = si-aqi
                elif ans[i] != si-aqi:
                    print(0)
                    exit()
        print(1)
    else:
        p1 = []
        m1 = []
        for i in range(1,n+1):
            if par[i] == 1:
                p1.append(ans[i])
            else:
                m1.append(ans[i])
        print(max(0,min(m1)+min(p1)-1))



    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
def bipar(graph,n,m):
  ls = [0]*(n+1)
  stack = [1]
  ls[1] = 1
  while stack:
    x = stack.pop()
    for y,_ in graph[x]:
      if ls[y] == 0:
        ls[y] = 3-ls[x]
        stack.append(y)
      elif ls[y] == ls[x]:
        return False
  return ls
color = bipar(graph,n,m)
if color != False:
  num = [10**18]*(n+1)
  num[1] = 0
  stack = [1]
  mn1 = 10**18
  mn2 = 10**18
  while stack:
    x = stack.pop()
    if color[x] == 1:
      mn1 = min(mn1,num[x])
    else:
      mn2 = min(mn2,num[x])
    for y,d in graph[x]:
      if num[y] == 10**18:
        num[y] = d-num[x]
        stack.append(y)
      elif num[x]+num[y] != d:
        print(0)
        exit()
  print(max(0,mn1+mn2-1))
else:
  num = [10**18]*(n+1)
  num[1] = 1
  stack = [1]
  flg = 0
  while stack:
    x = stack.pop()
    for y,d in graph[x]:
      if num[y] == 10**18:
        num[y] = d-num[x]
        stack.append(y)
      elif num[x]+num[y] != d:
        if not flg:
          s = num[x]
          t = num[y]
          z = (s+t-d)//2
          num = [10**18]*(n+1)
          stack = [x,y]
          num[x] = s-z
          num[y] = t-z
          while stack:
            x = stack.pop()
            for y,d in graph[x]:
              if num[y] == 10**18:
                num[y] = d-num[x]
                stack.append(y)
              elif num[x]+num[y] != d:
                print(0)
                exit()
          if min(num) > 0:
            print(1)
            exit()
        else:
          print(0)
          exit()
  if min(num) > 0:
    print(1)
  else:
    print(0)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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