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

Solution code:
#重み付きUnion-Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)

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

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*(n+1)
wei = [0]*(n+1)

ans=True
for i in range(m):
    p=[int(j) for j in input().split()]
    if same(p[0],p[1]):
        if diff(p[0],p[1])!=p[2]:
            ans=False
    else:
        unite(p[0],p[1],p[2])

if ans:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())

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

INF = 10 ** 10

# print(diff_dic)

ans_array = [INF] * N

for i in range(N):
    if ans_array[i] != INF:
        continue
    people_deque = deque()
    people_deque.append(i)
    if ans_array[i] == INF:
        ans_array[i] = 0
    while(len(people_deque)):
        # print(ans_array)
        person = people_deque.popleft()

        for v in diff_dic[person]:
            p, m = v
            if ans_array[p] == INF:
                ans_array[p] = ans_array[person] + m
                people_deque.append(p)
            elif ans_array[p] != (ans_array[person] + m):
                print("No")
                exit()
print("Yes")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,m = LI()
    a = LIR(n)
    ans = 0
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a.sort(key = lambda x:(-1)**i*x[0]+(-1)**j*x[1]+(-1)**k*x[2])
                p = [0,0,0]
                for l in range(m):
                    p[0] += a[l][0]
                    p[1] += a[l][1]
                    p[2] += a[l][2]
                p = abs(p[0])+abs(p[1])+abs(p[2])
                if p > ans:
                    ans = p
    print(ans)
    return

#B
def B():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y,su):
        x = root(x)
        y = root(y)
        su += comb_2(s[x])+comb_2(s[y])
        if rank[x] < rank[y]:
            s[y] += s[x]
            su -= comb_2(s[y])
            par[x] = y
        else:
            s[x] += s[y]
            su -= comb_2(s[x])
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return su

    def comb_2(a):
        return a*(a-1)//2

    n,m = LI()
    v = LIR(m)
    par = [i for i in range(n)]
    rank = [0]*n
    s = [1]*n
    su = comb_2(n)
    ans = [su]
    for a,b in v[:0:-1]:
        a -= 1
        b -= 1
        if root(a) != root(b):
            su = unite(a,b,su)
        ans.append(su)
    for i in ans[::-1]:
        print(i)
    return

#C
def C():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]

    def weight(x):
        root(x)
        return d[x]

    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    d = [0]*n
    for i in range(m):
        l,r,w = LI()
        l -= 1
        r -= 1
        if root(l) != root(r):
            unite(l,r,w)
        else:
            if weight(r)-weight(l) != w:
                print("No")
                return
    print("Yes")
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
node = [[]for i in range(N)]
for i in range(M):
    L,R,D = map(int,input().split())
    node[L-1].append([R-1,D])
    node[R-1].append([L-1,-D])
Flag = [False]*N
queue = deque([])
X = [0]*N
for i in range(N):
    if Flag[i] == False:
        Flag[i] = True
        queue.append(i)
        
        while queue != deque([]):
            p = queue.popleft()
            for r,d in node[p]:
                if Flag[r] == False:
                    Flag[r] = True
                    queue.append(r)
                    X[r] = X[p] - d
                elif X[r] != X[p] - d:
                    print('No')
                    exit()
print('Yes')

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    N, M = list(map(int, input().split()))
    MAX = 10**9
    L, R, D = [], [], []
    for i in range(M):
        _in = list(map(int, input().split()))
        L.append(_in[0])
        R.append(_in[1])
        D.append(_in[2])

    E = [{} for _ in range(N)]
    for i in range(M):
        E[L[i]-1][R[i]-1] = D[i]  # E[x1][x2] := x1からx2までの差
        E[R[i]-1][L[i]-1] = -D[i] # E[x2][x1] := x2からx1までの差
    
    V = [None] * N

    for i in range(N):
        if V[i] is not None:
            continue
        V[i] = 0
        q = [i]
        while q:
            j = q.pop()
            v = V[j]
            for k, d in E[j].items():
                if V[k] is None:
                    V[k] = v+d
                    q.append(k)
    ans = True
    for l, e in enumerate(E):
        for r, d in e.items():
            ans = ans and V[r]-V[l] == d
        if not ans:
            break
    print("Yes" if ans else "No")
        

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()
 
    G = [[] * (N+1) for _ in range(N+1) ]# 辺の保持
 
    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))
 
    # ある点からの距離
    x = [INF] * (N+1)
 
    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] == INF:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost
 
    for i in range(N):
        # if x[i] is not None: # 探索済み
        #     continue
        if x[i] == INF and dfs(i, 0) == False:
            print("No")
            return
    print("Yes")
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] for _ in range(N+1)]

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [INF] * (N+1)

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] == INF:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        # if x[i] is not None: # 探索済み
        #     continue
        if x[i] == INF and dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)


def dfs(s):
    global x, G
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            if not dfs(t):
                return False
        else:
            if x[t] != x[s] + d:
                return False
    return True


n, m = map(int, input().split())
x = [None] * n
G = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    G[l-1].append([r-1, d])
    G[r-1].append([l-1, -d])
res = True
for i in range(n):
    if x[i] is None:
        x[i] = 0
        res &= dfs(i)
print('Yes' if res==True else 'No')

Submission status: Accepted

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

E = [{} for _ in [0]*N]
for L,R,D in LRD:
    E[L-1][R-1] = D
    E[R-1][L-1] = -D

V = [None]*N
breakFlg = False
for i in range(N):
    if V[i]!=None:continue
    V[i] = 0
    q = [i]
    while q:
        j = q.pop()
        v = V[j]
        for k,d in E[j].items():
            if V[k] == None:
                V[k] = v+d
                q.append(k)
ans = True
for l,e in enumerate(E):
    for r,d in e.items():
        ans = ans and V[r]-V[l]==d
    if not ans:break
print("Yes" if ans else "No")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def f(v,p,G,T):
    global ans
    INF = 10**10
    for C in G[v]:
        c,d = C[0],C[1]
        if T[c]==INF:
            T[c] = T[v]+d
            f(c,v,G,T)
        elif T[c]!=T[v]+d:
            ans = "No"
def main():
    global ans
    N,M = map(int,input().split())
    G = [[] for i in range(N+1)]
    for i in range(M):
        L,R,D = map(int,input().split())
        G[L].append([R,D])
        G[R].append([L,-D])
    INF = 10**10
    T = [INF]*(N+1)
    while T.count(INF)!=0:
        for i in range(N+1):
            if T[i] == INF:
                T[i]=0
                f(i,-1,G,T)
        if ans=="No":break
ans = "Yes"
main()
print(ans)

Submission status: Accepted

Solution code:
def solve(n, query):
    for l, r, d in query:
        if is_same(l, r):
            if d != diff(l, r):
                return 'No'
        else:
            unite(l, r, d)
    return 'Yes'


def unite(x, y, w):
    w += diff_weight[x]-diff_weight[y]
    rt_x = find(x)
    rt_y = find(y)

    if rt_x == rt_y:
        return
    if rank[rt_x] >= rank[rt_y]:
        par[rt_y] = rt_x
        diff_weight[rt_y] = w
        if rank[rt_x] == rank[rt_y]:
            rank[rt_x] += 1
    else:
        par[rt_x] = rt_y
        diff_weight[rt_x] = -w


def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        diff_weight[x] += diff_weight[par[x]]
        par[x] = px
        return px


def weight(x):
    find(x)
    return diff_weight[x]


def is_same(x, y):
    return find(x) == find(y)


def diff(x, y):
    return weight(y)-weight(x)


if __name__ == '__main__':
    n, m = map(int, input().split())
    par, rank = [-1]*(n+1), [0]*(n+1)
    diff_weight = [0]*(n+1)
    query = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        query.append((l, r, d))
    print(solve(n, query))

Submission status: Accepted

Solution code:
def solve(n, query):
    for l, r, d in query:
        if is_same(l, r):
            if d != diff(l, r):
                return 'No'
        else:
            unite(l, r, d)
    return 'Yes'


def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        diff_weight[x] += diff_weight[par[x]]
        par[x] = px
        return px


def weight(x):
    find(x)
    return diff_weight[x]


def unite(x, y, w):
    w += diff_weight[x]-diff_weight[y]
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x, y = y, x
            w = -w
        par[x] += par[y]
        par[y] = x
        diff_weight[y] = w
        return True


def is_same(x, y):
    return find(x) == find(y)


def diff(x, y):
    return weight(y)-weight(x)


if __name__ == '__main__':
    n, m = map(int, input().split())
    par = [-1]*(n+1)
    diff_weight = [0]*(n+1)
    query = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        query.append((l, r, d))
    print(solve(n, query))

Submission status: Accepted

Solution code:
def main():
	N, M = map(int,input().split())
	if M == 0:
		print("Yes")
		return
	x = [[] for _ in range(N)]
	ans = [0 for _ in range(N)]
	for i in range(M):
		l, r, d = map(int, input().split())
		l, r = l-1, r-1
		x[l].append([r, d])
		x[r].append([l, -d])

	visited = [False for _ in range(N)]

	def dfs(i):
		vs = [i]
		while vs:
			v = vs.pop()
			for nex in x[v]:
				if not visited[nex[0]]:
					visited[nex[0]] = True
					ans[nex[0]] = ans[v]+nex[1]
					vs.append(nex[0])
				else:
					if ans[nex[0]] != ans[v]+nex[1]:
						return False
		return True

	ans_exist = True
	for i in range(N):
		if not visited[i]:
			visited[i] = True
			ans_exist = dfs(i)
		if not ans_exist:
			break

	if ans_exist:
		print("Yes")
	else:
		print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
LRD=[list(map(int,input().split())) for i in range(M)]
RDW=[[i,0,0] for i in range(N)]
ff=[0]
def compare(p,q,l):
    l_temp1=0
    l_temp2=0
    flag=0
    while(True):
        if q==p:
            flag=1
            break
        temp=RDW[q][0]
        if temp==q:
            break
        else:
            l_temp1+=RDW[q][2]
            q=temp
    if flag==0:
        while(True):
            if p==q:
                flag=1
                break
            temp=RDW[p][0]
            if temp==p:
                break
            else:
                l_temp2+=RDW[p][2]
                p=temp
    if flag==0:
        if RDW[p][1]>=RDW[q][1]:
            RDW[p][1]=max(RDW[p][1],RDW[q][1]+1)
            RDW[q][0]=p
            RDW[q][2]=l_temp2+l-l_temp1
        else:
            RDW[p][0]=q
            RDW[p][2]=-l_temp2-l+l_temp1
            l_temp2+l-l_temp1
    else:
        ll=l_temp1-l_temp2
        if l!=ll:
            ff[0]=1
for i in range(M):
    a,b,c=LRD[i]
    compare(a-1,b-1,c)
    if ff[0]==1:
        print("No")
        break
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append((l-1,d))
        e[l-1].append((r-1,-d))
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):
        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()
    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)
    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append((l-1,d))
        e[l-1].append((r-1,-d))
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):
        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append((l-1,d))
        e[l-1].append((r-1,-d))
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):
        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):

        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

graph = [{} for _ in range(N)]
for l, r, d in LRD:
	l, r = l - 1, r - 1
	graph[l][r] = d
	graph[r][l] = -d

visited = [False] * N
depths = [0] * N
def dfs(v):
	q = [v]
	while q:
		cu = q.pop()
		for nx, d in graph[cu].items():
			if visited[nx]:
				if depths[nx] != depths[cu] + d:
					return False
			else:
				visited[nx] = True
				depths[nx] = depths[cu] + d
				q += [nx]
	return True

for n in range(N):
	if not visited[n]:
		if not dfs(n):
			print("No")
			break
else:
	print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

graph = [{} for _ in range(N)]
for l, r, d in LRD:
	l, r = l - 1, r - 1
	graph[l][r] = d
	graph[r][l] = -d

visited = [False] * N
depths = [-1] * N
def dfs(v, p, d):
	if visited[v]:
		return True
	visited[v] = True
	depths[v] = d

	for n in graph[v]:
		if n == p:
			continue
		n_depth = d + graph[v][n]
		if depths[n] != -1 and depths[n] != n_depth:
			return False
		result = dfs(n, v, n_depth)
		if not result:
			return False
	return True

for n in range(N):
	if not dfs(n, -1, 0):
		print("No")
		break
else:
	print("Yes")

Submission status: Accepted

Solution code:
N, M = map(int,input().split())

connect = [[] for _ in range(N)]
visited = [False for _ in range(N)]
cord = [0 for _ in range(N)]

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

def dfs(i):
    q = [i]
    
    while q:
        x = q.pop()
        for nx, d in connect[x]:
            if not visited[nx]:
                visited[nx] = True
                cord[nx] = cord[x] + d
                q.append(nx)
            else:
                if cord[nx] != cord[x] + d:
                    return False
            
    return True

for i in range(N):
    if not visited[i]:
        visited[i] = True
        flag = dfs(i)
    if not flag:
        break

if flag:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
class WeightedUnionFind:

    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.level = [0] * n
        self.weight = [0] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            px = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = px
            return px

    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if self.level[px] < self.level[py]:
            self.par[px] = py
            self.weight[px] = -self.weight[x] + self.weight[y] + w
        else:
            self.par[py] = px
            self.weight[py] = + self.weight[x] - self.weight[y] - w
            if self.level[px] == self.level[py]:
                self.level[px] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

def solve(N, M):
    wuf = WeightedUnionFind(N+1)
    for i in range(M):
        L, R, D = map(int, input().split())
        if wuf.same(L, R):
            if wuf.diff(L, R) != D:
                return False
        else:
            wuf.union(L, R, D)
    return True

N, M = map(int, input().split())
if solve(N, M):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v):
    ret = True
    for u, d in es[v]:
        if x[u] == None:
            x[u] = x[v] + d
            ret = ret and dfs(u)
        elif x[u] != x[v] + d:
            return False
    return ret

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    L, R, D = map(int, input().split())
    es[L].append((R, D))
    es[R].append((L, -D))
x = [None for i in range(N+1)]
flag = True
for v in range(1, N+1):
    if x[v] == None:
        x[v] = 0
        if dfs(v) == False:
            flag = False
            break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.weight = [0 for _ in range(n + 1)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            y = self.find(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = y
            return y

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

        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.parent[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


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

wu = WeightedUnionFind(N)

for i in range(M):
    l, r, d = items[i]
    if wu.same(l, r):
        if d == wu.diff(l, r):
            continue
        else:
            print("No")
            exit()
    else:
        wu.union(l, r, d)

print("Yes")

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, size):
        self.parent = list(range(size))
        self.dist = [0] * size

    def find_root(self, x):
        if self.parent[x] == x:
            return x, 0
        else:
            self.parent[x], d = self.find_root(self.parent[x])
            self.dist[x] += d
            return self.parent[x], self.dist[x]

    def union(self, x, y, d):
        r1, d1 = self.find_root(x)
        r2, d2 = self.find_root(y)
        if r1 != r2:
            self.parent[r2] = r1
            self.dist[r2] = (d1 - d2) + d
        else:
            if (d2 - d1) != d:
                return False
        return True

def main():
    n, m = map(int, input().split())
    tree = UnionFindTree(n+1)
    for i in range(m):
        l, r, d = map(int, input().split())
        if not tree.union(l, r, d):
            print('No')
            return
    print('Yes')

main()

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    graph[r-1].append((l-1,-d))
    graph[l-1].append((r-1,d))
INF=10**9
x_list=[INF]*n
stack=[]
for i in range(n):
    if x_list[i]==INF:
        x_list[i]=0
        stack.append(i)
        while len(stack)>0:
            now=stack.pop()
            for j in graph[now]:
                if x_list[j[0]]==INF:
                    x_list[j[0]]=x_list[now]+j[1]
                    stack.append(j[0])
                else:
                    if x_list[j[0]]==x_list[now]+j[1]:
                        pass
                    else:
                        print('No')
                        sys.exit()
print('Yes')

Submission status: Accepted

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[1] > 10**9:
                    flag = False
                    break
                g[j[0]][1] += g[c[g[r][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[1] > 10**9:
                    flag = False
                    break
                g[j[0]][1] += g[c[g[l][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")