Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Runtime Error

Solution code:
n,m=(int(i) for i in input().split())

dic={}
id=1
k=0
ans=True

if m > 0:
  l,r,d = (int(i) for i in input().split())
  dic[id]={}
  dic[id][l]=0
  dic[id][r]=d

if m > 1:
  for j in range(m-1):
    l,r,d = (int(i) for i in input().split())
    flag=0
    for k in range(id):
      for i in dic.values():
        if l in i.keys():
            flag=1
            if r in i.keys():
                tmp1=dic[id][l]+d
                if tmp1 == dic[id][r]:
                    pass
                else:
                    ans=False
                    break
            else:
                tmp=dic[id][l]
                dic[id][r]=tmp+d
        else:
            if r in i.keys():
                flag=1
                dic[id][l]=dic[id][r]-d
    if flag==0:
        id+=1
        dic[id][l]=0
        dic[id][r]=d
    flag=0
    
print('Yes' if ans==True else 'No')

Submission status: Runtime Error

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]
        if r_pos > l_pos+d:
            for j in c[g[l][0]]:
                j[1] += r_pos - d - l_pos
                if j[i] > 10**9:
                    flag = False
                    break
            for j in c[g[r][0]]:
                g[j[0]][1] += g[c[g[l][0]][-1][0]][1] + 1
            c[g[r][0]].extend(c[g[l][0]])
            for j in c[g[l][0]]:
                g[j[0]][0] = g[r][0]

        else:
            for j in c[g[r][0]]:
                j[1] += l_pos + d - r_pos
                if j[i] > 10**9:
                    flag = False
                    break
            for j in c[g[l][0]]:
                g[j[0]][1] += g[c[g[r][0]][-1][0]][1] + 1
            c[g[l][0]].extend(c[g[r][0]])
            for j in c[g[r][0]]:
                g[j[0]][0] = g[l][0]

    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = g[c[g[l][0]][-2][0]][1]+1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = g[c[g[r][0]][-2][0]][1]+1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
    if not flag:
        break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]
        if r_pos > l_pos+d:
            for j in c[g[l][0]]:
                j[1] += r_pos - d - l_pos
            c[g[r][0]].extend(c[g[l][0]])
            g[l][0] = g[r][0]
            for j in c[g[r][0]]:
                g[j[0]][1] += g[c[g[l][0]][-1][0]][1] + 1
        else:
            for j in c[g[r][0]]:
                j[1] += l_pos + d - r_pos
            c[g[l][0]].extend(c[g[r][0]])
            g[r][0] = g[l][0]
            for j in c[g[l][0]]:
                g[j[0]][1] += g[c[g[r][0]][-1][0]][1] + 1
    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = g[c[g[l][0]][-2][0]][1]+1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = g[c[g[r][0]][-2][0]][1]+1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]
        if r_pos > l_pos+d:
            for j in c[g[l][0]]:
                j[1] += r_pos - d - l_pos
            c[g[r][0]].extend(c[g[l][0]])
            del c[g[l][0]]
            g_num -= 1
        else:
            for j in c[g[r][0]]:
                j[1] += l_pos + d - r_pos
            c[g[l][0]].extend(c[g[r][0]])
            del c[g[r][0]]
            g_num -= 1
    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = g[c[g[l][0]][-2][0]][1]+1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = g[c[g[r][0]][-2][0]][1]+1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]

        for j in c[g[r][0]]:
            j[1] += l_pos + d - r_pos
        c[g[l][0]].extend(c[g[r][0]])
        del c[g[r][0]]
    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = len(c[g[l][0]])-1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = len(c[g[r][0]])-1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]

        for j in c[g[r][0]]:
            j[1] += l_pos + d - r_pos
        c[g[l][0]].extend(c[g[r][0]])
        del c[g[r][0]]
    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = g[c[g[l][0]][-2][0]][1]+1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = g[c[g[r][0]][-2][0]][1]+1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [-1 for _ in range(n)]
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l] != -1 and g[r] != -1 and g[l] == g[r]:
        c_tmp = [_[0] for _ in c[g[l]]]
        if c[g[l]][c_tmp.index(r)][1] - c[g[l]][c_tmp.index(l)][1] != d:
            flag = False
            break
    elif g[l] != -1 and g[r] != -1:
        c_tmp = [_[0] for _ in c[g[l]]]
        l_pos = c[g[l]][c_tmp.index(l)][1]

        c_tmp = [_[0] for _ in c[g[r]]]
        r_pos = c[g[r]][c_tmp.index(r)][1]

        for j in range(len(c[g[r]])):
            c[g[r]][j][1] += l_pos + d - r_pos
        c[g[l]].extend(c[g[r]])
        del c[g[r]]
    elif g[l] != -1:
        c_tmp = [_[0] for _ in c[g[l]]]
        l_pos = c[g[l]][c_tmp.index(l)][1]
        c[g[l]].append([r, l_pos+d])
        g[r] = g[l]
    elif g[r] != -1:
        c_tmp = [_[0] for _ in c[g[r]]]
        r_pos = c[g[r]][c_tmp.index(r)][1]
        c[g[r]].append([l, r_pos-d])
        g[l] = g[r]
    else:
        c.append([[l, 0], [r, d]])
        g[l] = max(g)+1
        g[r] = g[l]
if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


class PotentialUnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.diffweight = [0 for i in range(N)]

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            self.diffweight[x] += self.diffweight[self.table[x]]
            return self.table[x]

    def Unite(self,x,y,w): #xとyをDiff(x,y)=W で繋げる
        w = w - self.Weight(y) + self.Weight(x)
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
            self.diffweight[y] = w
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            self.diffweight[x] = -w
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def Weight(self,x): # 重さ(根からの距離)
        self.Find(x)
        return self.diffweight[x]

    def Diff(self,x,y): # 繋がってる二点間距離
        return self.Weight(y) - self.Weight(x)


N,M = inpl()
PUF = PotentialUnionFind(100000)

for _ in range(M):
    l,r,d = inpl()
    if PUF.Check(l,r):
        if PUF.Diff(l,r) == d:
            continue
        else:
            print('No')
            exit()
    else:
        PUF.Unite(l,r,d)

print('Yes')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
l = dict()
tl = []
for i in range(n+1):
  l[i] = []
for _ in range(m):
  a,b,c = map(int,input().split())
  l[a].append((b,c))
  l[b].append((a,-c))
  tl.append((a,b,c))
pos = [None]*(n+1)

def dfs(v,p,pos):
  pos[v] = p
  for i,d in l[v]:
    if pos[i] == None:
      dfs(i,p+d,pos)
  return

for i in range(1,n+1):
  if pos[i] == None:
    dfs(i,0,pos)
for a,b,c in tl:
  if pos[b] - pos[a] != c:
    print("No")
    break
else:
  print("Yes")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = dict()
tl = []
for i in range(n+1):
  l[i] = []
for _ in range(m):
  a,b,c = map(int,input().split())
  l[a].append((b,c))
  l[b].append((a,-c))
  tl.append((a,b,c))
pos = [None]*(n+1)

def dfs(v,p,pos):
  pos[v] = p
  for i,d in l[v]:
    if pos[i] == None:
      dfs(i,p+d,pos)
  return

for i in range(1,n+1):
  if pos[i] == None:
    dfs(i,0,pos)
for a,b,c in tl:
  if pos[b] - pos[a] != c:
    print("No")
    break
else:
  print("Yes")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = dict()
tl = []
for i in range(n+1):
  l[i] = []
for _ in range(m):
  a,b,c = map(int,input().split())
  l[a].append((b,c))
  l[b].append((a,-c))
  tl.append((a,b,c))
pos = [None]*(n+1)

def dfs(v,p,pos):
  pos[v] = p
  for i,d in l[v]:
    if pos[i] == None:
      dfs(i,p+d,pos)
  return

for i in range(1,n):
  if pos[i] == None:
    dfs(i,0,pos)
for a,b,c in tl:
  if pos[b] - pos[a] != c:
    print("No")
    break
else:
  print("Yes")

Submission status: Runtime Error

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

N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[[] for i in range(N)]
for i in range(M):
    l,r,d=map(int,input().split())
    G[l-1].append((l-1,r-1,d))
x=[-1]*N
y=[1]*N
stack=deque()
for i in range(N):
    if y[i]:
        stack.extend(G[i])
        y[i]=0
    if len(stack)==0:
        continue
    while(stack):

        l,r,d=stack.popleft()

        if x[l]==-1:
            x[l]=0
        if x[r]==-1:
            x[r]=x[l]+d
            continue
        if x[r]!=x[l]+d:
            print("No")
            quit()
        stack.extend(G[r])
        y[r]=0
if max(x)>10**9:
    print("No")
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import collections
import sys
import copy

YES = "Yes"  # type: str
NO = "No"  # type: str

def get_dist(l,r,graph,prev_list,cur_dis):
    if l == r:
        return cur_dis
    elif l not in graph:
        return None
    else:
        for k,v in graph[l].items():
            if k not in prev_list:
                prev_list.append(l)
                dis = get_dist(k,r,graph,prev_list,cur_dis+v)
                if dis is not None:
                    return dis
    return None


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    graph = collections.defaultdict(dict)
    pos = {}

    for l, r, d in zip(L,R,D):
        graph[l][r] = d
        graph[r][l] = -d

    for l, r, d in zip(L,R,D):
        dd = get_dist(l, r, graph, [l], 0)
        if dd is not None and dd != d:
            print(NO)
            return

    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import collections
import sys
import copy

YES = "Yes"  # type: str
NO = "No"  # type: str

def get_dist(l,r,graph,prev_list,cur_dis):
    if l == r:
        return cur_dis
    elif l not in graph:
        return None
    else:
        for k,v in graph[l].items():
            if k not in prev_list:
                pl = copy.deepcopy(prev_list)
                pl.append(l)
                dis = get_dist(k,r,graph,pl,cur_dis+v)
                if dis is not None:
                    return dis
    return None


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    graph = collections.defaultdict(dict)
    pos = {}

    for l, r, d in zip(L,R,D):
        graph[l][r] = d
        graph[r][l] = -d

    for l, r, d in zip(L,R,D):
        dd = get_dist(l, r, graph, [l], 0)
        if dd is not None and dd != d:
            print(NO)
            return

    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import collections
import sys
sys.setrecursionlimit(10000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def get_dist(l,r,graph,prev,cur_dis):
    if l == r:
        return cur_dis
    elif l not in graph:
        return None
    else:
        for k,v in graph[l].items():
            if k != prev:
                dis = get_dist(k,r,graph,l,cur_dis+v)
                if dis is not None:
                    return dis
    return None


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    graph = collections.defaultdict(dict)
    pos = {}

    for l, r, d in zip(L,R,D):
        graph[l][r] = d
        graph[r][l] = -d

    for l, r, d in zip(L,R,D):
        dd = get_dist(l, r, graph, l, 0)
        if dd is not None and dd != d:
            print(NO)
            return

    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import collections

YES = "Yes"  # type: str
NO = "No"  # type: str

def get_dist(l,r,graph,prev,cur_dis):
    if l == r:
        return cur_dis
    elif l not in graph:
        return None
    else:
        for k,v in graph[l].items():
            if k != prev:
                dis = get_dist(k,r,graph,l,cur_dis+v)
                if dis is not None:
                    return dis
    return None


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    graph = collections.defaultdict(dict)
    pos = {}

    for l, r, d in zip(L,R,D):
        graph[l][r] = d
        graph[r][l] = -d

    for l, r, d in zip(L,R,D):
        dd = get_dist(l, r, graph, l, 0)
        if dd is not None and dd != d:
            print(NO)
            return

    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
g = {i: [] for i in range(n)}
for i in range(m):
    l, r, d = map(int, input().split())
    g[l - 1].append((r - 1, d))
    g[r - 1].append((l - 1, -d))
l = [-1] * n
l[0] = n
stack = [r]
s = set()
while stack:
    d = stack.pop()
    if d in s:
        continue
    for node, cost in g[d]:
        if l[node] == -1:
            l[node] = l[d] + cost
        else:
            if l[node] != l[d] + cost:
                print('No')
                exit()
        stack.append(node)
    s.add(d)
print('Yes')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        if idx > N:
            return False
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            ##t = con[0]
            ##d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                ##if vals[idx] is None:
                ##    vals[idx] = 0
                ##if vals[t] is None:
                ##    vals[t] = vals[idx] + d
                ##elif vals[t] != vals[idx] + d:
                ##    return False

                ##con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        if idx > N:
            return False
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                #if vals[idx] is None:
                #    vals[idx] = 0
                #if vals[t] is None:
                #    vals[t] = vals[idx] + d
                #elif vals[t] != vals[idx] + d:
                #    return False

                con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        if idx > N:
            return False
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                elif vals[t] != vals[idx] + d:
                    return False

                con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N + 1):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    cons = [[] for _ in range(N + 1)]
    for j in range(M):
        cons[R[j]].append([L[j], -D[j], False])
        cons[L[j]].append([R[j], D[j], False])

    vals = [None] * (N + 1)
    visited = [False] * (N + 1)
    #print(cons)

    def dfs(idx):
        #print(idx)
        #print(visited)
        #print(vals)
        #print()
        visited[idx] = True
        #for t, d, used in cons[idx]:
        for con in cons[idx]:
            t = con[0]
            d = con[1]
            used = con[2]
            if not used:
                #print(idx, t, d, vals[idx], vals[t])
                if vals[idx] is None:
                    vals[idx] = 0
                if vals[t] is None:
                    vals[t] = vals[idx] + d
                if vals[t] != vals[idx] + d:
                    return False
                con[2] = True
                if not visited[t]:
                    dfs(t)
        return True

    ret = YES
    for i in range(1, N):
        if not visited[i]:
            res = dfs(i)
            if not res:
                ret = NO
                break
    #print(cons)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
a=int(input())
b=int(input())
c=int(input())
x=int(input())
cnt=0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i + 100*j + 50*k==x:
        cnt+=1
print(cnt)