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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200002)

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

graph = [[] for i in range(n)]
for i in range(m):
    l, r, d = list(map(int, input().split()))

    graph[l-1].append([r-1, d])
    graph[r-1].append([l-1, -d])
# print(graph)


def dfs(s):
    for t, d in graph[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


x = [None]*n
ans = True
for i in range(n):
    if x[i] is None:
        x[i] = 0
        if not dfs(i):
            ans = False

print(('No', 'Yes')[ans])

Submission status: Accepted

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

# it watches only end of union
# for i in range(m):
#     l,r,d = map(int, input().split())
#     if ml[l] == -1 and ml[r] == -1:
#         ml[l] = 0
#         ml[r] = d
#     elif ml[l] != -1 and ml[r] == -1:
#         ml[r] = d + ml[l]
#         if ml[r] > n:
#             print('R', i, ml[l], ml[r], flush=True)
#             print('No', flush=True)
#             sys.exit()
#     elif ml[l] == -1 and ml[r] != -1:
#         ml[l] = ml[r] - d
#         if ml[l] < 1:
#             print('L', i, ml[l], ml[r], flush=True)
#             print('No', flush=True)
#             sys.exit()
#     else:
#         if ml[r] - ml[l] != d:
#             print('B', i, l, ml[l], r, ml[r], d, flush=True)
#             print('No', flush=True)
#             sys.exit()
# print('Yes', flush=True)

class UnionfindWithWeight():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
        self.dist=[0]*n
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.dist[x],self.parents[x]
    def union(self,x,y,d):
        rx=self.find(x)[-1]
        ry=self.find(y)[-1]
        diff=d+self.dist[x]-self.dist[y]
        if rx==ry:
            if diff!=0:
                return True
            return False
        if self.ranks[ry]>self.ranks[rx]:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=rx
        self.dist[ry]=diff
        if self.ranks[ry]==self.ranks[rx]:
            self.ranks[rx]+=1
        return False
lrd = []
for i in range(m):
    l,r,d = list(map(int, input().split()))
    lrd.append([l,r,d])
v=UnionfindWithWeight(n)
for i in lrd:
    l, r, d = i
    if v.union(l-1,r-1,d):
        print('No')
        import sys
        sys.exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]

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

    x = [None] * n

    for i in range(n):
        if x[i] is not None:
            continue
        x[i] = 0
        q = deque()
        q.append(i)

        while q:
            u = q.popleft()
            for v, d in adj[u]:
                if x[v] is None:
                    q.append(v)
                    x[v] = x[u] + d
                elif x[v] != x[u] + d:
                    print("No")
                    exit()
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[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)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

for _ in range(M):
  L, R, D = map(int, input().split())
  if wuf.same(L, R):
    if wuf.diff(L, R) != D:
      print("No")
      exit()
  else:
    wuf.union(L, R, D)

print("Yes")

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    F = [set() for _ in range(N)]
    T = set(i for i in range(N))
    for _ in range(M):
        L, R, D = read_values()
        L -= 1
        R -= 1
        F[L].add((R, D))
        T.discard(R)
    C = [-1] * N
    for t in T:
        S = deque()
        S.append(t)
        C[t] = 0
        while S:
            p = S.popleft()
            for q, d in F[p]:
                if C[q] == -1:
                    S.append(q)
                    C[q] = C[p] + d
                    continue
                if C[p] + d != C[q]:
                    print("No")
                    return
    if C.count(-1) > 0:
        print("No")
    else:
        print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class PotentializedUnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent", "potential_diff"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
        self.potential_diff = [0] * (size + 1) # potential_diff[node] = potential[parent[node]] - potential[node]
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in reversed(path):
            self.potential_diff[child] += self.potential_diff[self.parent[child]]
            self.parent[child] = a
        return a

    def union(self, a, b, diff):
        """
        connect a and b, where potential of these satisfy `potential[b] - potential[a] == diff`,
        Returning `not same(a, b)`. 
        
        If a and b are already in the same tree, then this does nothing.
        """

        a_root = self.find(a)
        b_root = self.find(b)
        diff += self.potential_diff[b] - self.potential_diff[a] # find で経路圧縮しているのでこれでよい。
        a = a_root
        b = b_root

        if a == b:
            return False 
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
                self.potential_diff[a] = diff
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
                self.potential_diff[b] = -diff
            else:
                self.parent[a] = b #bのほうが大きい
                self.potential_diff[a] = diff
            return True
        
    def same(self, a, b):
        return self.find(a) == self.find(b)

    def diff(self, a, b):
        assert self.find(a) == self.find(b) # find(a) と find(b) 内での経路圧縮が本質なので、コメントアウトしない。
        return self.potential_diff[a] - self.potential_diff[b]


def main():
    import sys
    input = sys.stdin.buffer.readline
    
    N, M = map(int, input().split())
    lrds = list(map(int, sys.stdin.buffer.read().split()))
    puf = PotentializedUnionFind(N)
    ls = lrds[::3]
    rs = lrds[1::3]
    ds = lrds[2::3]
    for l, r, d in zip(ls, rs, ds):
        if not puf.union(l, r, d):
            if not puf.diff(l, r) == d:
                print("No")
                exit()
    
    print("Yes")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    #重み付き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
    wei = [0]*n

    for i in range(m):
        l,r,d = map(int,input().split())
        l,r = l-1,r-1
        if same(l,r):
            if d != diff(l,r):
                print('No')
                exit()
        else:
            unite(l,r,d)
    print('Yes')
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#重み付きUnion-Findによる実装
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#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,readline().split())
#0-index
par = [-1]*N
wei = [0]*N
for _ in range(M):
    l,r,d = map(int,readline().split())
    l,r = l-1,r-1
    if same(l,r):
        if d != diff(l,r):
            print('No')
            exit()
    else:
        unite(l,r,d)
print('Yes')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
### 幅優先探索により矛盾を探す
import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

dist = [0]*N
done = [0]*N  
def bfs(i):
    q = deque([i])
    while q:
        x = q.popleft()
        for y,d in graph[x]:
            if done[y] == 0:
                done[y] = 1
                dist[y] = dist[x]+ d
                q.append(y)
            else:
                if dist[y] != dist[x]+d:
                    return 0
    return 1

for i in range(N):
    if done[i] == 0:
        done[i] = 1
        if bfs(i) == 0:
            print('No')
            sys.exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
G = [[] for n in range(N)]

for m in range(M):
  a,b,d = map(int,input().split())
  G[a-1].append((b-1,d))
  G[b-1].append((a-1,-d))

X = [None]*N

def dfs(i, x=0):
  for j, d in G[i]:
    if X[j] is None:
      X[j] = x+d
      dfs(j, x+d)
    elif X[j] != x+d:
      print("No")
      exit()

for n in range(N):
  if X[n] is not None:
    continue
  X[n] = 0
  dfs(n)

print("Yes")

Submission status: Accepted

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

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

    def unite(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
    
f=lambda:map(int,input().split())
N,M=f()
wuf=WeightedUnionFind(N+1)

flg=True
for _ in [0]*M:
    l,r,w=f()
    if wuf.is_same_group(l,r):
        if wuf.diff(l,r)!=w:
            flg=False
    else:
        wuf.unite(l,r,w)
    if not flg:
        break
print(['No','Yes'][flg])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
LRD = [tuple(int(x) for x in input().split()) for _ in range(M)]
Graph = [[] for _ in range(N)]
for l,r,d in LRD:
    Graph[r-1].append((l-1,d))
    Graph[l-1].append((r-1,-d))

seen = set()
Dfr = [0] * N #dist from Root
for root in range(N):
    if root in seen: continue
    seen.add(root)
    V = [root]
    while len(V) != 0: #bfs
        v = V.pop(0)
        for nv,d in Graph[v]:
            if nv in seen and Dfr[nv] != Dfr[v] + d: #bfsで発見済みの値が異なる⇔矛盾
                print('No')
                exit()
            if nv in seen: continue
            else:
                seen.add(nv)
                Dfr[nv] = Dfr[v] + d
                V.append(nv)
print('Yes')

Submission status: Accepted

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

n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
    l, r, d = map(int, input().split())
    graph[l].append([r, d])
    graph[r].append([l, -d])
place = [None for i in range(n + 1)]

num = 0
flag = True
while num <= n:
    if flag == False:
        break
    if place[num] != None:
        num += 1
        continue
    place[num] = 0
    queue = collections.deque([num])
    while queue:
        if flag == False:
            break
        test = queue.popleft()
        for i in graph[test]:
            if place[i[0]] != None:
                if place[i[0]] - place[test] != i[1]:
                    flag = False
                    break
            else:
                place[i[0]] = place[test] + i[1]
                queue.append(i[0])
    else:
        num += 1
if flag == True:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((-c,u))
vals = [None] * n
def dijkstra(start):
    h = [start]
    vals[start] = 0
    ans = True
    while h:
        u = h.pop()
        for d, v in ns[u]:
            if vals[v] is None:
                vals[v] = vals[u]+d
                h.append(v)
            else:
                if vals[v]!=vals[u]+d:
                    return False
    return ans

for start in range(n):
    if vals[start] is not None:
        continue
    res = dijkstra(start)
    if not res:
        print("No")
        break
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((-c,u))
vals = [None] * n
def dijkstra(start):
    import heapq
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    ans = True
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
            else:
                if vals[v]!=val+d:
                    return False
    return ans

for start in range(n):
    if vals[start] is not None:
        continue
    res = dijkstra(start)
    if not res:
        print("No")
        break
else:
    print("Yes")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class WeightedUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

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

    def union(self, x, y, w):
        w += self.weight[x] - self.weight[y]
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y, w = y, x, -w
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.weight[y] = w
        return

    def weig(self, x):
        self.find(x)
        return self.weight[x]

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

(n, m), *q = [[*map(int, o.split())] for o in open(0)]
UF = WeightedUnionFind(n + 1)
for l, r, d in q:
    if UF.same(l, r):
        if d != abs(UF.diff(l, r)):
            print("No"); exit()
    else:
        UF.union(l, r, d)
print("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = LI()
    G[l - 1] += [(r - 1, d)]
    G[r - 1] += [(l - 1, -d)]

A = [0] * n
visited = [0] * n
for i in range(n):
    if visited[i]:
        continue
    visited[i] = 1
    A[i] = 0
    q = [i]
    while q:
        u = q.pop()
        for v, di in G[u]:
            if visited[v]:
                if A[v] != A[u] + di:
                    print("No")
                    exit()
            else:
                A[v] = A[u] + di
                visited[v] = 1
                q += [v]

print("Yes")

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N, M = map(int, input().split())
graph = [[] for i in range(N)]
root = [-float("inf")] * N
for i in range(M):
  l, r, d = map(int, input().split())
  graph[l - 1].append([r - 1, d])
  graph[r - 1].append([l - 1, -d])
  
  
for i in range(N):
  if root[i] < -10 ** 10:
    root[i] = 0
    queue = [i]
    while queue:
      now = heappop(queue)
      for j, k in graph[now]:
        if root[j] < - 10 ** 10:
          root[j] = root[now] + k
          heappush(queue, j)
        elif root[j] == root[now] + k:
          continue
        else:
          print("No")
          quit()
          
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  l,r,d = map(int, input().split())
  l,r = l-1,r-1
  E[l].append((r,d))
  E[r].append((l,-d)) 
  
#for e in E:
#  print(e)
  
# bfs
Q = deque()
visited = [False] * N
willSearch = [False] * N
INF = 10**16
A = [ INF ] * N

for i in range(N):
  if visited[i]:
    continue
  Q.append((i,-1,0))
  while Q:
    now, prev, num = Q.popleft()
    visited[now] = True
    if A[now] == INF:
      A[now] = num
    elif A[now] != num:
      # ある点において2通りのnum設定の仕方がある
      #print(now,prev,num,A[inxt])
      print("No")
      exit(0)
    for nxt, dis in E[now]:
      if nxt == prev:
        continue
      if A[nxt] < INF and A[nxt] != num + dis:
        # ある点において2通りのnum設定の仕方がある
        #print(now,prev,num, nxt,dis, A[nxt])
        print("No")
        exit(0)
      if visited[nxt] or willSearch[nxt]:
        continue
      Q.append((nxt, now, num + dis))
      willSearch[nxt] = True
    
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  l,r,d = map(int, input().split())
  l,r = l-1,r-1
  E[l].append((r,d))
  E[r].append((l,-d)) 
  
#for e in E:
#  print(e)
  
# bfs
Q = deque()
visited = [False] * N
willSearch = [False] * N
INF = 10**16
A = [ INF ] * N

for i in range(N):
  if visited[i]:
    continue
  Q.append((i,-1,0))
  while Q:
    now, prev, num = Q.popleft()
    visited[now] = True
    if A[now] == INF:
      A[now] = num
    elif A[now] != num:
      # ある点において2通りのnum設定の仕方がある
      #print(now,prev,num,A[inxt])
      print("No")
      exit(0)
    for nxt, dis in E[now]:
      if nxt == prev:
        continue
      if A[nxt] < INF and A[nxt] != num + dis:
        # ある点において2通りのnum設定の仕方がある
        #print(now,prev,num, nxt,dis, A[nxt])
        print("No")
        exit(0)
      if visited[nxt] or willSearch[nxt]:
        continue
      Q.append((nxt, now, num + dis))
      willSearch[nxt] = True
    
print("Yes")

Submission status: Accepted

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.ranks=[0]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.dist[x],self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[-1]
        ry=self.find(y)[-1]
        diff=d+self.dist[x]-self.dist[y]
        if rx==ry:
            if diff!=0:
                return True
            return False
        if self.ranks[ry]>self.ranks[rx]:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=rx
        self.dist[ry]=diff
        if self.ranks[ry]==self.ranks[rx]:
            self.ranks[rx]+=1
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Accepted

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.dist[x],self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Accepted

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        _,rx=self.find(x)
        _,ry=self.find(y)
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Accepted

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x,self.dist[x]
        else:
            tmp=self.find(self.parents[x])
            self.parents[x]=tmp[0]
            self.dist[x]+=tmp[1]
            return self.parents[x],self.dist[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[0]
        ry=self.find(y)[0]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Accepted

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()