Problem:


Score : 600 points

Problem Statement

Kenkoooo found a simple connected graph.
The vertices are numbered 1 through n.
The i-th edge connects Vertex u_i and v_i, and has a fixed integer s_i.

Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:

For every edge i, the sum of the positive integers written in Vertex u_i and v_i is equal to s_i.

Find the number of such ways to write positive integers in the vertices.

Constraints

2 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq u_i < v_i \leq n

2 \leq s_i \leq 10^9

If i\neq j, then u_i \neq u_j  or v_i \neq v_j.

The graph is connected.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

n m
u_1 v_1 s_1
:
u_m v_m s_m

Output

Print the number of ways to write positive integers in the vertices so that the condition is satisfied.

Sample Input 1

3 3
1 2 3
2 3 5
1 3 4

Sample Output 1

1

The condition will be satisfied if we write 1,2 and 3 in vertices 1,2 and 3, respectively.
There is no other way to satisfy the condition, so the answer is 1.

Sample Input 2

4 3
1 2 6
2 3 7
3 4 5

Sample Output 2

3

Let a,b,c and d be the numbers to write in vertices 1,2,3 and 4, respectively.
There are three quadruples (a,b,c,d) that satisfy the condition:

(a,b,c,d)=(1,5,2,3)

(a,b,c,d)=(2,4,3,2)

(a,b,c,d)=(3,3,4,1)

Sample Input 3

8 7
1 2 1000000000
2 3 2
3 4 1000000000
4 5 2
5 6 1000000000
6 7 2
7 8 1000000000

Sample Output 3

0



Sample input:
3 3
1 2 3
2 3 5
1 3 4


Sample output:
1

Submission status: Runtime Error

Solution code:
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 = (
    1 if 1 - W_min <= d < B_min else
    0 if d is None else
    max(0, W_min + B_min - 1)
)

print(ans)

Submission status: Runtime Error

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(n)]
    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: Runtime Error

Solution code:
function BattleSprite:moveToPosIdx(posIdx)
	local x, y
	if posIdx <= 6 then
		x, y = self.StandingPos[posIdx].x, self.StandingPos[posIdx].y
	else
		x, y = CC_DESIGN_RESOLUTION.width-self.StandingPos[posIdx-6].x, self.StandingPos[posIdx-6].y
	end
	if x and y then
		self:setPosition(cc.p(x,y))
		self:setCurPos(cc.p(x,y))
	end
end

Submission status: Runtime Error

Solution code:
@parallel
@roles('allgame')
def _last_redis_save():
	with cd(get_deploy_path()):
		redisSet = set()
		ret = run('supervisorctl status')
		for line in ret.split('\n'):
			line = line.strip()
			if line.find('RUNNING') >= 0 and line.find('redis') >= 0:
				name = line.split()[0].strip()
				redisSet.add(name)

		ret = []
		with cd('db'):
			for redis in sorted(list(redisSet)):
				port = redis[5:]
				ret.append(run('ls -l -h game%s.rdb' % port))
		return '\n'.join(ret)

def last_redis_save():
	result = execute(_last_redis_save)
	for k in sorted(result.keys()):
		print '-'*20
		print k, ':'
		v = result[k]
		print v

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
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)

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

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

Submission status: Runtime Error

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)
          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 =[(ano,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: Runtime Error

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
          zan = [[float("inf"),float("inf")] for i in range(n)]
          zan[a] = (ano,0)
          zan[i] = (ino,(j)-zan[a][1])
          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 =[(ano,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: Runtime Error

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
          zan = [[float("inf"),float("inf")] for i in range(n)]
          zan[a] = (ano,0)
          zan[i][0] = ino
          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 =[(ano,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: Runtime Error

Solution code:
import copy
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)]
cost2 = copy.deepcopy(cost)
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
          zan = [[float("inf"),float("inf")] for i in range(n)]
          zan[a] = (ano,0)
          zan[i][0] = ino
          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 =[(ano,0)]
  while len(tan):
      i,j = tan.pop()
      for a,b in cost2[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: Runtime Error

Solution code:
from collections import defaultdict

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

s = defaultdict(set)
for i in range(m):
    a, b, c = map(int, input().split())
    s[a - 1].add((b - 1, c))
    s[b - 1].add((a - 1, c))

s = sorted(s.items())

p = {s[0][0]: (1, 0)}
u = 0


def search_route(u):
    check = 0
    temp_sign = p[u][0]
    temp_value = p[u][1]
    for a, b in s[u][1]:
        if a not in p:
            p[a] = (temp_sign * -1, b - temp_value)
            check = search_route(a)
        elif p[a][0] == temp_sign:
            check = 1
        elif p[a][1] != b - temp_value:
            print('0')
            exit()
    return check


check = search_route(0)

res_max = float('inf')
res_min = 0
for i in range(n):
    temp = p[i]
    if temp[0] == 1 and temp[1] < res_min:
        res_min = temp[1]
    elif temp[0] == -1 and temp[1] < res_max:
        res_max = temp[1]

if check == 0:
    print(max(0, res_max + res_min - 1))
else:
    print('1')

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

s = defaultdict(set)
for i in range(m):
  a, b, c = map(int, input().split())
  s[a - 1].add((b - 1, c))
  s[b - 1].add((a - 1, c))

s = sorted(s.items())

p = {s[0][0]: (1, 0)}
u = 0

def search_route(u):
  check = 0
  temp_sign = p[u][0]
  temp_value = p[u][1]
  for a, b in s[u][1]:
    if a not in p:
      p[a] = (temp_sign * -1, b - temp_value)
      check = search_route(a)
    elif p[a][0] == temp_sign:
        check = 1
    elif p[a][1] != b - temp_value:
        print('0')
        exit()
  return check

check = search_route(0)

res_max = float('inf')
res_min = 0
for i in range(n):
  temp = p[i]
  if temp[0] == 1 and temp[1] < res_min:
    res_min = temp[1]
  elif temp[0] == -1 and temp[1] < res_max:
    res_max = temp[1]

if check == 0:
    print(max(0, res_max + res_min - 1))
else:
    print('1')

Submission status: Runtime Error

Solution code:
def LI(): return list(map(int, input().split()))
n, m = LI()
rinsetsu = [[] for i in range(n)]
for i in range(m):
    u, v, s = LI()
    rinsetsu[u-1].append([v-1, s, i])
    rinsetsu[v-1].append([u-1, s, i])
upper = []
lower = []
visited = set([])
def dfs(index, before, even):
    all_flag = True
    for tonari, s, id_ in rinsetsu[index]:
        if id_ not in visited:
            if even:
                next_before = s - before
                upper.append(next_before)
            else:
                next_before = before - s
                lower.append(next_before)
                next_before = -next_before
            next_index = tonari
            visited.add(id_)
            dfs(next_index, next_before, even==False)
            all_flag = False
    if all_flag:
        return
        

dfs(index=0, before=0, even=True)
up = min(upper)
low = max(max(lower), 0)
if up < low or up < 0:
    print(0)
else:
    print(up-low-1)

Submission status: Runtime Error

Solution code:
n,m=list(map(int, input().strip().split()))
links=[[]for _ in range(n)]
checked={}
for i in range(m):
    u,v,s=list(map(int, input().strip().split()))
    links[u-1].append((v-1,s))
    links[v-1].append((u-1,s))
    checked[u-1,v-1]=False
    checked[v-1,u-1]=False
current=0
visited=[False]*n

sikis=[None for _ in range(n)]
sikis[0]=(0,1)
Q=[(0,l,s) for l,s in links[0]]

ans=-1
count=-1
while Q:
    u,v,cst=Q.pop()
    if checked[u,v]:continue
    visited[u]=True
    checked[u,v]=True
    checked[v,u]=True
    su = sikis[u]
    sv=(cst-su[0],su[1]*(-1))
    if not sikis[v]:
        sikis[v]=sv
    else:
        svo=sikis[v]
        if ans > 0:
            if val(svo,ans)!=val(sv,ans):
                pass
            else:
                ans=-1
                count=0
                break
        else:
            if svo[1]==sv[1]:# 係数同じ
                if svo[0]==sv[0]:
                    pass
                else:
                    ans=-1
                    count=0
                    break
            else:# 係数違う
                if svo[1]==-1:
                    ans2=(svo[0]-sv[0])
                else:
                    ans2=(sv[0]-svo[0])
                if ans2%2!=0 or ans2<0:
                    ans=-1
                    count=0
                    break
                else:
                    ans=ans2//2
    if not visited[v]:
        for l,s in links[v]:
            if not checked[v,l]:
                Q.append([v,l,s])
if count==0:
    print(0)
elif ans>0:
    print(1)
else:
    minnum=1
    maxnum=float("inf")
    for sk in sikis:
        if sk[1]<0:
            maxnum=min(maxnum,sk[0]-1)
        if sk[1]>0:
            minnum=max(minnum,-sk[0]+1)
    count=maxnum-minnum+1
    print(max(0,count))

Submission status: Runtime Error

Solution code:
n,m=list(map(int, input().strip().split()))
links=[[]for _ in range(n)]
checked={}
for i in range(m):
    u,v,s=list(map(int, input().strip().split()))
    links[u-1].append((v-1,s))
    links[v-1].append((u-1,s))
    checked[u-1,v-1]=False
    checked[v-1,u-1]=False
current=0
visited=[False]*n

sikis=[None for _ in range(n)]
sikis[0]=(0,1)
Q=[(0,l,s) for l,s in links[0]]

ans=-1
count=-1
while Q:
    u,v,cst=Q.pop()
    if checked[u,v]:continue
    visited[u]=True
    checked[u,v]=True
    checked[v,u]=True
    su = sikis[u]
    sv=(cst-su[0],su[1]*(-1))
    if not sikis[v]:
        sikis[v]=sv
    else:
        svo=sikis[v]
        if ans > 0:
            if val(svo,ans)!=val(sv,ans):
                pass
            else:
                ans=-1
                count=0
                break
        else:
            if svo[1]==sv[1]:# 係数同じ
                if svo[0]==sv[0]:
                    pass
                else:
                    ans=-1
                    count=0
                    break
            else:# 係数違う
                if svo[1]==-1:
                    ans2=(svo[0]-sv[0])
                else:
                    ans2=(sv[0]-svo[0])
                if ans2%2!=0 or ans2<0:
                    ans=-1
                    count=0
                    break
                else:
                    ans=ans2//2
    if not visited[v]:
        for l,s in links[v]:
            if not checked[v,l]:
                Q.append([v,l,s])
t2=time.time()
if count==0:
    print(0)
elif ans>0:
    print(1)
else:
    minnum=1
    maxnum=float("inf")
    for sk in sikis:
        if sk[1]<0:
            maxnum=min(maxnum,sk[0]-1)
        if sk[1]>0:
            minnum=max(minnum,-sk[0]+1)
    count=maxnum-minnum+1
    print(max(0,count))

Submission status: Runtime Error

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

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        pu(f[1])
        col = [0] * (n + 1)
        col[f[1]] = 1
        par = [None] * (n + 1)
        while st:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if x == f[1] and z == f[0]:
                    s = dat[y/3*3+2]
                elif not col[z]:
                    col[z] = 1
                    par[z] = (x, dat[y/3*3+2])
                    pu(z)
                y = xt[y]
        k = []
        x, z = f
        while x != z:
            k.append(par[x][1])
            x = par[x][0]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[x] = z
        pu(z)
        while st:
            x = po()
            if dp[x] < 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    col = [0] * (n + 1)
    pu(1)
    while st:
        x = po()
        if not col[x]:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(z)
                y = xt[y]
        else:
            lo, hi = 1, 1001001001
            col[x] = 2
            y = la[x]
            while y is not None:
                z = dat[y]
                if col[z] == 2:
                    s = dat[y/3*3+2]
                    l, h = s - dp[z][1], s - dp[z][0]
                    if lo < l:
                        lo = l
                    if hi > h:
                        hi = h
                y = xt[y]
            dp[x] = (lo, hi)
    ans = dp[1][1] - dp[1][0] + 1
    if ans < 0:
        ans = 0
    print ans
main()