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:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,=pin()
    A=tupin()
    B=[A[i]-i-1 for i in range(N)]
    
    if N%2:
        d=[B[N//2]]
    else:d=[B[N//2-1],B[N//2]]

    
    c=10**10
    point=-1
    for b in d:
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            #print(b,temp)
    print(c)
    """
    c=10**10
    point=-1
    for b in range(min(B),max(B)+1):
        temp=0
        for x in B:
            temp+=abs(x-b)
        if temp<c:
            point=b
            c=temp
            print(b,temp)
    """
#%%submit!
resolve()

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int,input().split())
parent= [i for i in range(N)]
depth = [0 for i in range(N)]
distance = [0 for i in range(N)]

def find(i):
    if i == parent[i]:
        return i, 0
    p, d = find(parent[i])
    depth[i] = d + 1
    return p, d + 1

def distance(i, d):
    while i != parent[i]:
        distance[i] += d
        i = parent[i]

def merge(i, j, d):
    r_i, d_i = find(i)
    r_j, d_j = find(j)
    if r_i == r_j:
        return distance[j] - distance[i] == d
    if d_i < d_j:
        parent[r_i] = r_j
        _, _ = find(i)
        td = distance[j] - d - distance[i]
        distance(i, td)
    else:
        parent[r_j] = r_i
        _, _ = find(j)
        td = distance[i] + d - distance[j]
        distance(j, td)
    return True

for _ in range(M):
    L, R, D = map(int,input().split())
    if not merge(L-1, R-1, D):
        print('No')
        sys.exit()
print('Yes')

Submission status: Runtime Error

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    L_R_D_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        L_R_D_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    L_R_D_arr.sort()
    iter_ = [float('inf')]*(N+1)

    TF = 'No'
    iter_[L_R_D_arr[0][0]] = 0
    for L, R, D in L_R_D_arr:
        if iter_[R] not in [float('inf'),iter_[L]+D]:
            break
        else:
            iter_[R] = iter_[L]+D
    else:
        TF = 'Yes'
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
INFTY = 10**10
A = sorted([list(map(int,input().split())) for _ in range(M)],key=lambda x:x[0])
hist = [0 for _ in range(N)]
dist = [-INFTY for _ in range(N)]
hist[A[0][0]]=1
dist[A[0][0]] = 0
hist[A[0][1]]=1
dist[A[0][1]] = dist[A[0][0]]+A[0][2]
flag = 0
for j in range(1,M):
    ind = A[i][0]
    ind2 = A[i][1]
    if hist[ind]==1:
        if hist[ind2]==1:
            if dist[ind2]==dist[ind]+A[i][2]:
                continue
            else:
                flag = 1
                break
        else:
            dist[ind2] = dist[ind]+A[i][2]
            hist[ind2] = 1
    else:
        if hist[ind2]==1:
            dist[ind] = dist[ind2]-A[i][2]
            hist[ind]=1
        else:
            dist[ind] = 0
            hist[ind] = 1
            dist[ind2] = A[i][2]
            hist[ind2]=1
if flag==0:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# 12:17-12:28 give up -> kaisetu
# 13:18-14:08 chudan
# 15:29-16:50

import sys

sys.setrecursionlimit(10000)


def main():
    N, M = map(int, input().split())
    L, R, D = [None] * M, [None] * M, [None] * M
    for i in range(M):
        L[i], R[i], D[i] = map(int, input().split())
        L[i] -= 1  # 1-index -> 0_index
        R[i] -= 1  # 1-index -> 0_index

    dist_infos = {}
    for l, r, d in zip(L, R, D):
        if l in dist_infos:
            dist_infos[l][r] = d
        else:
            dist_infos[l] = {r: d}

        if r in dist_infos:
            dist_infos[r][l] = -d
        else:
            dist_infos[r] = {l: -d}

    xs = [None] * N

    fixed = set([])

    def rec(node):
        fixed.add(node)

        if xs[node] is None:  # if start node
            xs[node] = 0
        
        if xs[node] is None and node not in dist_infos:
            return None
        
        # 隣接するノードでまだfixしていないもの
        adj_node_infos = {
            adj: d for adj, d in dist_infos[node].items() if adj not in fixed
        }

        for adj, d in adj_node_infos.items():
            if xs[adj] is None:
                xs[adj] = xs[node] + d
            elif xs[adj] != xs[node] + d:
                print("No")
                exit()

            rec(adj)

    for key in dist_infos.keys():
        rec(key)

    print("Yes")

    
main()

Submission status: Runtime Error

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# 12:17-12:28 give up -> kaisetu
# 13:18-14:08 chudan
# 15:29-16:50


def main():
    N, M = map(int, input().split())
    L, R, D = [None] * M, [None] * M, [None] * M
    for i in range(M):
        L[i], R[i], D[i] = map(int, input().split())
        L[i] -= 1  # 1-index -> 0_index
        R[i] -= 1  # 1-index -> 0_index

    dist_infos = {}
    for l, r, d in zip(L, R, D):
        if l in dist_infos:
            dist_infos[l][r] = d
        else:
            dist_infos[l] = {r: d}

        if r in dist_infos:
            dist_infos[r][l] = -d
        else:
            dist_infos[r] = {l: -d}

    xs = [None] * N

    fixed = set([])

    def rec(node):
        fixed.add(node)

        if xs[node] is None:  # if start node
            xs[node] = 0
        
        if xs[node] is None and node not in dist_infos:
            return None
        
        # 隣接するノードでまだfixしていないもの
        adj_node_infos = {
            adj: d for adj, d in dist_infos[node].items() if adj not in fixed
        }

        for adj, d in adj_node_infos.items():
            if xs[adj] is None:
                xs[adj] = xs[node] + d
            elif xs[adj] != xs[node] + d:
                print("No")
                exit()

            rec(adj)

    for key in dist_infos.keys():
        rec(key)

    print("Yes")

    
main()

Submission status: Runtime Error

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# 12:17-12:28 give up -> kaisetu
# 13:18-14:08 chudan
# 15:29-16:06


def main():
    N, M = map(int, input().split())
    L, R, D = [None] * M, [None] * M, [None] * M
    for i in range(M):
        L[i], R[i], D[i] = map(int, input().split())
        L[i] -= 1  # 1-index -> 0_index
        R[i] -= 1  # 1-index -> 0_index

    dist_infos = {}
    for l, r, d in zip(L, R, D):
        if l in dist_infos:
            dist_infos[l][r] = d
        else:
            dist_infos[l] = {r: d}

        if r in dist_infos:
            dist_infos[r][l] = -d
        else:
            dist_infos[r] = {l: -d}

    xs = [None] * N

    node_queue = [0]
    n_queue = 1
    fixed = set([])
    n_fixed = 0
    while True:
        if n_queue == 0:
            if n_fixed == N:
                return "Yes"

            for i in range(N):
                if xs[i] is None:
                    node_queue.append(i)
                    n_queue += 1
                    break

        node = node_queue[-1]
        del node_queue[-1]
        n_queue -= 1
        fixed.add(node)
        n_fixed += 1
        
        if node not in dist_infos:
            # start and terminal
            xs[node] = 0
            continue

        if xs[node] is None:
            xs[node] = 0

        adj_node_infos = {
            k: d for k, d in dist_infos[node].items() if k not in fixed
        }

        for adj, d in adj_node_infos.items():
            if xs[adj] is None:
                xs[adj] = xs[node] + d
            elif xs[adj] != xs[node] + d:
                return "No"

            node_queue.append(adj)
            n_queue += 1


print(main())

Submission status: Runtime Error

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


N, M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in LRD:
    l, r, d = el
    G[l].append((r, d))
    G[r].append((l, -d))
#print(G)

seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child, dist in G[parent]:
        group[-1].append((parent, child, dist))
        if seen[child] == False:
            dfs(child)


group =[]
for i in range(1, N + 1):
    if seen[i] == False:
        group.append([])
        dfs(i)
#print(group)
G.clear()

mujun = 0
zahyo = [None] * (N + 1)
for lst in group:
    if len(lst) > 2:
        zahyo[lst[0][0]] = 0
        for relation in lst:
            #print(zahyo)
            l, r, dist = relation
            if zahyo[r] != None:
                if zahyo[l] + dist != zahyo[r]:
                    mujun = 1
            else:
                zahyo[r] = zahyo[l] + dist

if mujun == 1:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

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

N, M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in LRD:
    l, r, d = el
    G[l].append((r, d))
    G[r].append((l, -d))
#print(G)

seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child, dist in G[parent]:
        group[-1].append((parent, child, dist))
        if seen[child] == False:
            dfs(child)


group =[]
for i in range(1, N + 1):
    if seen[i] == False:
        group.append([])
        dfs(i)
#print(group)
G.clear()

mujun = 0
zahyo = [None] * (N + 1)
for lst in group:
    if len(lst) > 2:
        zahyo[lst[0][0]] = 0
        for relation in lst:
            #print(zahyo)
            l, r, dist = relation
            if zahyo[r] != None:
                if zahyo[l] + dist != zahyo[r]:
                    mujun = 1
            else:
                zahyo[r] = zahyo[l] + dist

if mujun == 1:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

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

N, M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in LRD:
    l, r, d = el
    G[l].append((r, d))
    G[r].append((l, -d))
#print(G)

seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child, dist in G[parent]:
        if parent < child:
            group[-1].append((parent, child, dist))
        if seen[child] == False:
            dfs(child)


group =[]
for i in range(1, N + 1):
    if seen[i] == False:
        group.append([])
        dfs(i)
print(group)

mujun = 0
zahyo = [None] * (N + 1)
for lst in group:
    if len(lst) > 2:
        zahyo[lst[0][0]] = 0
        for relation in lst:
            #print(zahyo)
            l, r, dist = relation
            if zahyo[r] != None:
                if zahyo[l] + dist != zahyo[r]:
                    mujun = 1
            else:
                zahyo[r] = zahyo[l] + dist

if mujun == 1:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in LRD:
    l, r, d = el
    G[l].append((r, d))
#print(G)

seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True

    for child, dist in G[parent]:
        group[-1].append((parent, child, dist))
        if seen[child] == False:
            dfs(child)


group =[]
for i in range(1, N + 1):
    if seen[i] == False:
        group.append([])
        dfs(i)
#print(group)

mujun = 0
for lst in group:
    if len(lst) >= 3:
        dct = {}
        dct[lst[0][0]] = 0
        for relation in lst:
            l, r, dist = relation
            if r in dct:
                if dct[l] + dist != dct[r]:
                    mujun = 1
            else:
                dct[r] = dct[l] + dist

if mujun == 1:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math

# 標準入力の取得
N,M = list(map(int, input().split()))
L,R,D = [],[],[]
for m in range(M):
    L_n,R_n,D_n = list(map(int, input().split()))
    L.append(L_n)
    R.append(R_n)
    D.append(D_n)

# 求解処理
# 与えられた情報に沿って、組（x_1, x_2, ・・・, x_N）を作成していき、矛盾が生じるかどうか判定する。
# 初期リストの作成
x = [math.nan for n in range(N)]

# x_L1 = 0で初期化
if M >= 1:
    x[L[0]-1] = 0

# 与えられた情報に沿って、各xを埋めていく
is_correct = True
for i in range(M):
    x_Ri = x[L[i]-1] + D[i]
    # 矛盾があるかどうか判定
    if (not math.isnan(x[R[i]-1])) and (x[R[i]-1] != x_Ri):
        is_correct = False
        break
    x[R[i]-1] = x_Ri

# 結果出力
if is_correct:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# D - People on a Line
# モジュールのインポート
import math
import sys

# 標準入力の取得
N,M = list(map(int, input().split()))
if M == 0:
    print("Yes")
    sys.exit()
L,R,D = [],[],[]
for m in range(M):
    L_n,R_n,D_n = list(map(int, input().split()))
    L.append(L_n)
    R.append(R_n)
    D.append(D_n)

# 求解処理
# 与えられた情報に沿って、組（x_1, x_2, ・・・, x_N）を作成していき、矛盾が生じるかどうか判定する。
# 初期リストの作成
x = [math.nan for n in range(N)]

# x_L1 = 0で初期化
x[L[0]-1] = 0

# 与えられた情報に沿って、各xを埋めていく
is_correct = True
for i in range(M):
    x_Ri = x[L[i]-1] + D[i]
    # 矛盾があるかどうか判定
    if (not math.isnan(x[R[i]-1])) and (x[R[i]-1] != x_Ri):
        is_correct = False
        break
    x[R[i]-1] = x_Ri

# 結果出力
if is_correct:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
jud = True
kyori = [0 for _ in range(n)]
reached = [False for _ in range(n)]
rightl = [[] for _ in range(n)]
rightdis = [[] for _ in range(n)]
leftl = [0 for _ in range(n)]
for i in range(m):
	l, r, d = map(int, input().split())
	rightl[l-1].append(r-1)
	rightdis[l-1].append(d)
	leftl[r-1] += 1

def dfs(x):
	global jud
	p = len(rightl[x])
	if p != 0:
		for j in range(p):
			q = rightl[x][j]
			if reached[q] == False:
				reached[q] = True
				kyori[q] = kyori[x] + rightdis[x][j]
				dfs(q)
			else:
				if kyori[q] != kyori[x] + rightdis[x][j]:
					jud = False
	return
for i in range(n):
	if leftl[i] == 0:
		reached[i] = True
		dfs(i)

jud2 = True
for i in range(n):
	if reached[i] == False:
		jud2 = False

if jud & jud2:
	print("Yes")
else:
	print("No")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
jud = True
kyori = [0 for _ in range(n)]
reached = [False for _ in range(n)]
rightl = [[] for _ in range(n)]
rightdis = [[] for _ in range(n)]
leftl = [0 for _ in range(n)]
for i in range(m):
	l, r, d = map(int, input().split())
	rightl[l-1].append(r-1)
	rightdis[l-1].append(d)
	leftl[r-1] += 1
print(rightl)
print(rightdis)

def dfs(x):
	global jud
	p = len(rightl[x])
	if p != 0:
		for j in range(p):
			q = rightl[x][j]
			if reached[q] == False:
				print(x,q)
				reached[q] = True
				kyori[q] = kyori[x] + rightdis[x][j]
				dfs(q)
			else:
				if kyori[q] != kyori[x] + rightdis[x][j]:
					print(q,x,"false")
					jud = False
	return
for i in range(n):
	if leftl[i] == 0:
		reached[i] = True
		dfs(i)
		
jud2 = True
for i in range(n):
	if reached[i] == False:
		jud2 = False

if jud & jud2:
	print("Yes")
else:
	print("No")

Submission status: Runtime Error

Solution code:
from copy import deepcopy
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    edge[x].append([y,z])
    edge[y].append([x,-z])

dist = [-1] * N
ans = ["Yes"]
def dfs(pv, v, d):
    if dist[v] < 0:
        dist[v] = d
    elif dist[v] != d:
        ans[0] = "No"

    for i, nv in enumerate(edge[v]):
        if pv == nv[0]:
            continue
        if nv[1] == 10 ** 9:
            continue
        nd = edge[v][i][1]
        edge[v][i][1] = 10 ** 9
        dfs(v, nv[0], d+nd)

for i in range(N):
    if dist[i] == -1:
        dfs(-1,i,0)
print(*ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
def dfs(l,d):
    loc[l]=d
    for n_l,n_d in way[l]:
        if loc[n_l]==10**9:
            dfs(n_l,d+n_d)
        elif loc[n_l]!=d+n_d:
            print("No")
            exit()

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

way=[[] for i in range(N)]
loc=[10**9]*N

for _ in range(M):
    L,R,D=map(int,input().split())
    way[L-1].append([R-1,D])
    way[R-1].append([L-1,-D])

for i in range(N):
    if loc[i]==10**9:
        dfs(i,0)

print("Yes")

Submission status: Runtime Error

Solution code:
from sys import exit
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
#まだ訪問してなければTrue
check=[True]*n
#どこと関係があるかを記録する(maybe right)
lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
#wrong thought
#どっちも決まってない場合の処理
#決まってるとこからやれば良い
#ソートして順番に決めておく

#記録した関係から辿っていく
#まず初めのやつ
st=-1
for i in range(n):
    if len(lrd[i])>=1:
        st=i
        break
if st==-1:
    print("Yes")
    exit()
def bfs(z):
    global lrd,check,x
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])
        else:
            if x[k[0]]!=x[z]+k[1]:
                print("No")
                exit()
x[st]=0
check[st]=False
bfs(st)

print("Yes")

Submission status: Runtime Error

Solution code:
from sys import exit
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
#まだ訪問してなければTrue
check=[True]*n
#どこと関係があるかを記録する(maybe right)
lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
#wrong thought
#どっちも決まってない場合の処理
#決まってるとこからやれば良い
#ソートして順番に決めておく

#記録した関係から辿っていく
#まず初めのやつ
st=-1
for i in range(n):
    if len(lrd[i])>=1:
        st=i
        break
if st==-1:
    print("Yes")
    exit()
def bfs(z):
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])
        else:
            if x[k[0]]!=x[z]+k[1]:
                print("No")
                exit()
x[st]=0
check[st]=False
bfs(st)

print("Yes")

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;

bool dfs(int i, vector<vector<pint>>& L, vector<vector<pint>>& R, vector<bool>& visited , vector<int>& X) {
    bool ans = true;
    for (pint r : L[i]) {
        int j = r.first;
        int d = r.second;
        if (visited[j]) {
            visited[j] = false;
            X[j] = X[i] + d;
            ans = (ans && dfs(j,L,R,visited,X));
        }
        else {
            if (X[j] - X[i] != d) {
                ans = false; break;
            }
        }
    }
    
    for (pint l : R[i]) {
        int j = l.first;
        int d = l.second;
        if (visited[j]) {
            visited[j] = false;
            X[j] = X[i] - d;
            ans = (ans && dfs(j,L,R,visited,X));
        }
        else {
            if (X[i] - X[j] != d) {
                ans = false; break;
            }
        }
    }
    return ans;
}

int main() {
    int n,m; cin >> n >> m;
    vector<vector<pint>> L(n);
    vector<vector<pint>> R(n);

    for (int i = 0; i < m; i ++ ) {
        int l,r,d;
        cin >> l >> r >> d;
        l --; r --;
        L[l].push_back({r,d});
        R[r].push_back({l,d});
    }

    vector<bool> visited(n,true);
    vector<int> X(n,0);
    
    bool ans = true;
    for (int i = 0; i < n; i ++) {
        if (visited[i]) {
            visited[i] = false;
            ans = (ans&&dfs(i,L,R,visited,X));
        }
    }

    if (ans) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque

def main(): 
    n,m = map(int,input().split())
    L = [[] for _ in range(n)]
    R = [[] for _ in range(n)]
    for _ in range(m):
        l,r,d = map(int,input().split())
        l -= 1
        r -= 1
        L[l].append((r,d))
        R[r].append((l,d))
    
    visited = [True] * n
    X = [0] * n

    def dfs(i):
        ans = True
        for r in L[i]:
            j, d = r
            if visited[j]:
                X[j] = X[i] + d
                visited[j] = False
                ans = (ans&dfs(j)) 
            else:
                if X[j] - X[i] != d:
                    ans = False
                    break
        for l in R[i]:
            j,d = l
            if visited[j]:
                X[j] = X[i] - d
                visited[j] = False
                ans = (ans&dfs(j))
            else:
                if X[i] - X[j] != d:
                    ans = False
                    break
        return ans
    
    ans = True
    for i in range(n):
        if visited[i]:
            visited[i] = False
            ans = (ans&dfs(i))
    
    if ans:
        print('Yes')
    else:
        print('No')        
  
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
People = {x+1:[] for x in range(10**6+1)}

for _ in range(m):
    l, r, d = map(int, input().split())
    People[l].append([r, d])
    People[r].append([l, -d])

Place = ['x' for _ in range(10**6+1)]

min_num = 10**7
for i in range(1,n+1):
    if len(People[i]) == 0:
        pass
    else:
        min_num = min(min_num, i)

if m != 0:
    Place[min_num] = 0
    ans = 'Yes'
    for i in range(1,10**6+1):
        Related = People[i]
        for related in Related:
            person = related[0]
            place = related[1]
            if Place[person] == 'x':
                Place[person] = Place[i] + place
            elif Place[person] != Place[i] + place:
                ans = 'No'
                break
else:
    ans = 'Yes'

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
People = {x+1:[] for x in range(10**6+1)}

for _ in range(m):
    l, r, d = map(int, input().split())
    People[l].append([r, d])
    People[r].append([l, -d])

Place = ['x' for _ in range(10**6+1)]

min_num = 10**7
for i in range(1,n+1):
    if len(People[i]) == 0:
        pass
    else:
        min_num = min(min_num, i)

if m != 0:
    Place[min_num] = 0
    ans = 'Yes'
    for i in range(min_num,min_num+n):
        Related = People[i]
        for related in Related:
            person = related[0]
            place = related[1]
            if Place[person] == 'x':
                Place[person] = Place[i] + place
            elif Place[person] != Place[i] + place:
                ans = 'No'
                break
else:
    ans = 'Yes'

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
People = {x+1:[] for x in range(10**6+1)}

for _ in range(m):
    l, r, d = map(int, input().split())
    People[l].append([r, d])
    People[r].append([l, -d])

Place = ['x' for _ in range(10**6+1)]

min_num = 10**7
for i in range(1,n+1):
    if len(People[i]) == 0:
        pass
    else:
        min_num = min(min_num, i)
        break
if m != 0:
    Place[min_num] = 0
    ans = 'Yes'
    for i in range(min_num,min_num+n):
        Related = People[i]
        for related in Related:
            person = related[0]
            place = related[1]
            if Place[person] == 'x':
                Place[person] = Place[i] + place
            elif Place[person] != Place[i] + place:
                ans = 'No'
                break
else:
    ans = 'Yes'

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
LRD = [None] * M
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L][R] = D
    LRD[i] = (L, R, D)
dist = floyd_warshall(G)
for L, R, D in LRD:
    if dist[L][R] != D or dist[R][L] != float('inf'):
        print('No')
        exit()
print('Yes')

Submission status: Runtime Error

Solution code:
import queue

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

dis = [[] for i in range(n)]

for i in range(m):
    g1,g2,L =  map(int,input().split())
    dis[g1-1].append((g2-1,L))
    dis[g2-1].append((g1-1,-L))




geo = [0.5] * n

q = queue.Queue()


for i in range(m):
    if geo[i] == 0.5:
        q.put(i)
        while not q.empty():
            g1 = q.get()
            for g2,L in dis[g1]:
                if geo[g2] == 0.5:
                    geo[g2] = geo[g1] + L
                    q.put(g2)
                else:
                    if geo[g2] != geo[g1] + L:
                        print("No")
                        exit()
print("Yes")



"""
q = queue.Queue(0)
for i in range(1,5):
    q.put(i)
q.put(4)
while not q.empty():
    print(q.get())
"""

Submission status: Runtime Error

Solution code:
################
class UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots:全ての根の要素を返す
    group_count():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
################

from collections import defaultdict

N,M=map(int,input().split())
uf = UnionFind(N)
L=[0]*N
R=[0]*N
D=[0]*N
x=[-1]*N

f=1

for i in range(M):
    L[i],R[i],D[i]=map(int,input().split())
    L[i]-=1
    R[i]-=1
    uf.union(L[i],R[i])
    if x[L[i]]==-1 and x[R[i]]==-1:
        x[L[i]]=0
        x[R[i]]=D[i]
    elif x[L[i]]==-1:
        x[L[i]]=x[R[i]]-D[i]
    elif x[R[i]]==-1:
        x[R[i]]=x[L[i]]+D[i]
    else:
        if x[R[i]]-x[L[i]]!=D[i]:
            f=0
    
#範囲の判定

cnt_g=uf.group_count()
Max = defaultdict(int)
Min  = defaultdict(int)


for i in range(N):
    gi=uf.find(i)
    xx=x[i]
    Max[gi]=max(Max[gi],xx)
    Min[gi]=min(Min[gi],xx)
    
inf=10**9    


roots=uf.roots()

for i in roots:
    l=Max[i]-Min[i]
    if l>inf:
        f=0
    
    
            
            
            
if f==1:
    print("Yes")
else:
    print("No")