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:
class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    self.rank=[0]*n
    self.wrong=0

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      if self.weigh(y)-self.weigh(x)!=w:
        self.wrong=1
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
        self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
          
N,M=map(int,input().split())
wuf=WeightsUnionfind(N)
F=0
for m in range(M):
  l,r,d=map(int,input().split())
  wuf.unite(l-1,r-1,d)
if wuf.wrong==1:
  print("No")
else:
  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):  # 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  # 親

    # 併合
    # (xからyへの重みがw) = (y - x = W)
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # 既に同集合の場合
        if rx == ry:
            if self.diff(x, y) != w:
                print("No")
                exit()
        # 木の高さで処理を変えるのは高速化(木を低くする)のため
        # 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[x] - self.weight[y]
            # 木の高さが同じだった場合の処理
            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]

    def show(self):
        for i in range(1, n + 1):
            print("node:{} par:{} w:{}".format(i, union.par[i], union.weight[i]))


n, m = [int(i) for i in input().split()]
l = [0 for i in range(m)]
r = [0 for i in range(m)]
d = [0 for i in range(m)]

union = WeightedUnionFind(n)
for i in range(m):
    l[i], r[i], d[i] = [int(i) for i in input().split()]
    union.union(l[i], r[i], d[i])
print("Yes")
#union.show()

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):  # 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  # 親

    # 併合
    # (xからyへの重みがw) = (y - x = W)
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # 既に同集合の場合
        if rx == ry:
            if self.diff(x, y) != w:
                print("No")
                exit()
        # 木の高さで処理を変えるのは高速化(木を低くする)のため
        # 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]

    def show(self):
        for i in range(1, n + 1):
            print("node:{} par:{} w:{}".format(i, union.par[i], union.weight[i]))


n, m = [int(i) for i in input().split()]
l = [0 for i in range(m)]
r = [0 for i in range(m)]
d = [0 for i in range(m)]

union = WeightedUnionFind(n)
for i in range(m):
    l[i], r[i], d[i] = [int(i) for i in input().split()]
    union.union(l[i], r[i], d[i])
print("Yes")
#union.show()

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):  # 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 #親

    # 併合
    # (xからyへの重みがw) = (y - x = W)
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # 既に同集合の場合
        if rx == ry:
            if self.diff(x, y) != w:
                print("No")
                exit()
        # 木の高さで処理を変えるのは高速化(木を低くする)のため
        # 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 = [int(i) for i in input().split()]
l = [0 for i in range(m)]
r = [0 for i in range(m)]
d = [0 for i in range(m)]

union = WeightedUnionFind(n)
for i in range(m):
    l[i], r[i], d[i] = [int(i) for i in input().split()]
    union.union(l[i], r[i], d[i])
print("Yes")
#for i in range(1, n+1):
    #print("{} par:{} w:{}".format(i, union.par[i], union.weight[i]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def DFS(start):
    global graph
    global zahyou

    start_num=zahyou[start]

    for w,d in graph[start]:
        if(zahyou[w]==None):
            zahyou[w]=start_num + d
            if( not DFS(w)):
                return False
        else:
            if(start_num + d != zahyou[w]):
                return False
    
    return True
            


n,m=map(int,input().split())
graph=[[] for _ in range(n)]

zahyou=[None]*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,-1*d))

flag=True
for i in range(n):
    if(zahyou[i]==None):
        zahyou[i]=0
        flag&=DFS(i)
        if( not flag):
            break

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    V[R-1] += 1
dist = [-1]*N
for i in range(N):
    if V[i]:
        continue
    S = [i]
    dist[i] = 0
    while S:
        v = S.pop()
        for u, d in E[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + d
                S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

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

Submission status: Accepted

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

class WeightedUnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self.weight = [0] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            pa = self.root(self.parent[a])
            self.weight[a] += self.weight[self.parent[a]]
            self.parent[a] = pa
            return pa
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b,w):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self.weight[ra] = w - self.weight[a] + self.weight[b]
        else:
            self.parent[rb] = ra
            self.weight[rb] = -w - self.weight[b] + self.weight[a]
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    def diff(self,a,b):
        return self.weight[a] - self.weight[b]

wuf = WeightedUnionFind(N)
for l,r,d in src:
    l,r = l-1, r-1
    if wuf.is_same(l,r):
        if d != wuf.diff(l,r):
            print('No')
            exit()
    else:
        wuf.unite(l,r,d)
print('Yes')

Submission status: Accepted

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

par = [i for i in range(n)]
rank = [0 for i in range(n)]
diff_weight = [0 for i in range(n)]


def root(x):
    if par[x] == x:
        return x
    r = root(par[x])
    diff_weight[x] += diff_weight[par[x]]
    par[x] = r
    return par[x]

def issame(x, y):
    return root(x) == root(y)

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

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

def merge(x, y, w):
    w += weight(x)
    w -= weight(y)
    x = root(x)
    y = root(y)
    if x == y:
        return False
    if rank[x] < rank[y]:
        x, y = y, x
        w = -w
    if rank[x] == rank[y]:
        rank[x] += 1
    par[y] = x
    diff_weight[y] = w
    return True

for i in range(m):
    l, r, d = map(int, input().split())
    if issame(l-1, r-1):
        di = diff(l-1, r-1)
        if di != d:
            print("No")
            exit()
    else:
        merge(l-1, r-1, d)

print("Yes")

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()

graph = [[] for _ in range(n)]
for _ in range(m):
    l,r,d = li()
    l -= 1
    r -= 1
    graph[l].append((d,r))
    graph[r].append((-d,l))
    
searched = [False]*n
dist = [float("inf") for _ in range(n)]

exist = True
for i in range(n):
    if not searched[i]:
        dist[i] = 0
        searched[i] = True
        stack = [(0,i)]
        
        while stack:
            cost, cur = stack.pop()
            for nex_cost, nex_node in graph[cur]:
                if searched[nex_node]:
                    if cost + nex_cost != dist[nex_node]:
                        exist = False
                        
                else:
                    stack.append((cost+nex_cost, nex_node))
                    dist[nex_node] = cost + nex_cost
                    searched[nex_node] = True
                    


print("Yes") if exist else print("No")

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()

graph = [[] for _ in range(n)]
for _ in range(m):
    l,r,d = li()
    l -= 1
    r -= 1
    graph[l].append((d,r))
    graph[r].append((-d,l))
    
searched = [False]*n
dist = [float("inf") for _ in range(n)]

exist = True
for i in range(n):
    if not searched[i]:
        dist[i] = 0
        searched[i] = True
        stack = [(0,i)]
        
        while stack:
            cost, cur = stack.pop()
            for nex_cost, nex_node in graph[cur]:
                if searched[nex_node]:
                    if cost + nex_cost != dist[nex_node]:
                        exist = False
                        
                else:
                    stack.append((cost+nex_cost, nex_node))
                    dist[nex_node] = cost + nex_cost
                    searched[nex_node] = True
                    
if exist:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
es = [{} for i in range(N)]
for l,r,d in src:
    es[l-1][r-1] = d
    es[r-1][l-1] = -d

dist = [None] * N
for i in range(N):
    if dist[i] is not None: continue
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        for to,d in es[v].items():
            if dist[to] is not None:
                if dist[to] != dist[v]+d:
                    print('No')
                    exit()
                continue
            dist[to] = dist[v]+d
            stack.append(to)
print('Yes')

Submission status: Accepted

Solution code:
import sys

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

#UnionFind

Group=[(i,0) for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
 
def find(x):#x→(x,d):xよりd右にある、と帰る.
    ANS=0
    while Group[x][0] != x:
        ANS+=Group[x][1]
        x=Group[x][0]
        
    return (x,ANS)

def Union(x,y,d):#xとyが同じグループになるよう更新
    if x>y:
        x,y,d=y,x,-d
    if find(x)[0]!=find(y)[0]:
        reach=min(find(x)[0],find(y)[0])

        if find(x)[0]!=reach:
            #if find(y)[1]-d-find(x)[1]<0:
            #    print("w",find(y)[1]-d-find(x)[1])
            #    return False
            
            Group[find(x)[0]]=(reach,find(y)[1]-d-find(x)[1])


        else:
            #if find(x)[1]+d-find(y)[1]<0:
            #    print("q",find(y)[1]-d-find(x)[1])
            #    return False
            
            Group[find(y)[0]]=(reach,find(x)[1]+d-find(y)[1])



    else:
        if find(x)[1]+d != find(y)[1]:
            #print(x,y,find(x),find(y),d)
            return False

    Group[y]=(x,d)
    return True

for l,r,d in LRD:
    #print(Group)
    if Union(l,r,d)==False:
        print("No")
        sys.exit()

print("Yes")

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class WeightedUnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        self.diff_weight = [0 for i in range(self.n)]
        
    # ノードxのルートを求める
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            r = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return self.par[x]
        
    # ノードxのルートからの距離を求める
    def weight(self, x:int) -> int:
        self.find(x)
        return self.diff_weight[x]
        
    # weight(y) - weight(x) = w となるようにする
    def unite(self, x:int, y:int, w:int) -> bool:
        if self.isSame(x,y):
            return False
        
        w += self.weight(x)
        w -= self.weight(y)
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            w = -w

        self.par[ry] = self.par[rx]
        self.diff_weight[ry] = w
        
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    def diff(self, x:int, y:int) -> int:
        if self.isSame(x,y):
            return self.weight(y)-self.weight(x)
        else:
            raise ValueError("xとyは同じ木に属していません")


n,m = li()

lrd = []
for _ in range(m):
    l,r,d = li()
    l -= 1
    r -= 1
    lrd.append((l,r,d))
 
exist = True

wuf = WeightedUnionFind(n)

for l,r,d in lrd:
    wuf.unite(l,r,d)
    if wuf.diff(l,r) != d:
        exist = False
        break
    
if exist:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import queue
inf = float('inf')
N,M = map(int,input().split())
edge = {}
for i in range(N):
    edge[i] = {}
for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    edge[L][R] = D
    edge[R][L] = -D

x = [inf for i in range(N)]

def bfs(n):
    que = queue.Queue()
    que.put(n)
    x[n] = 0
    ans = True
    while que.qsize():
        L = que.get()
        for R in edge[L]:
            if x[R] != inf:
                if x[R] != x[L]+edge[L][R]:
                    ans = False
            else:
                x[R] = x[L]+edge[L][R]
                que.put(R)
    return ans
for n in range(N):
    if x[n] == inf:
        ans = bfs(n)
        if not ans:
            break

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# ---
class UnionFind:
    __slots__ = ['nodes', 'weight']

    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # ノードの値が負の場合ルートを表し、値は木のランクを表す
        self.weight = [0] * size  # ノードx -> ルート(ノードx)への重みを表す

    # 検索
    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            parent = self.find(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = parent
            return parent

    # 併合
    # def unite(self, x: int, y: int, w: int) -> bool:
    #     root_x = self.find(x)
    #     root_y = self.find(y)
    #     if root_x == root_y:
    #         return False
    #     else:
    #         rank_x = -self.nodes[root_x]
    #         rank_y = -self.nodes[root_y]
    #         if rank_x < rank_y:
    #             self.nodes[root_x] = root_y
    #             self.weight[root_x] = w - self.weight[y] - self.weight[x]
    #         else:
    #             self.nodes[root_y] = root_x
    #             self.weight[root_y] = w - self.weight[x] - self.weight[y]
    #
    #             if rank_x == rank_y:
    #                 self.nodes[root_x] += -1
    #
    #         return True

    # xとyのルートが等しい時: 入力された重みwが正しいかどうかを判定
    # xとyのルートが異なる時: xとyを併合する
    # True: 併合，False: 何もしない，ValueError: 入力された重みに矛盾がある
    def relate(self, x: int, y: int, w: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            # 入力された重みwに矛盾がないか判定
            if self.weight[x] - self.weight[y] == w:
                return False
            raise ValueError
        else:
            rank_x = -self.nodes[root_x]
            rank_y = -self.nodes[root_y]
            if rank_x < rank_y:
                self.nodes[root_x] = root_y
                self.weight[root_x] = w + self.weight[y] - self.weight[x]
            else:
                self.nodes[root_y] = root_x
                self.weight[root_y] = -w + self.weight[x] - self.weight[y]

                if rank_x == rank_y:
                    self.nodes[root_x] += -1
            return True

    # UnionFind木の一覧を返す
    # def get_tree(self) -> dict:
    #     tree = {}
    #     for i, node in enumerate(self.nodes):
    #         if node < 0:
    #             if i not in tree.keys():
    #                 tree[i] = []
    #         else:
    #             if self.find(node) in tree.keys():
    #                 tree[self.find(node)].append(i)
    #             else:
    #                 tree[self.find(node)] = [i]
    # 
    #     return tree


N, M = inpl()
uf = UnionFind(N)
relate = uf.relate
try:
    for i in range(M):
        l, r, d = inpl()
        relate(l - 1, r - 1, d)
    else:
        print('Yes')
except ValueError:
    print('No')

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# ---
class UnionFind:
    __slots__ = ['nodes', 'weight']

    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size
        self.weight = [0] * size

    # 検索
    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            parent = self.find(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = parent
            return parent

    # 併合
    # def unite(self, x: int, y: int, w: int) -> bool:
    #     root_x = self.find(x)
    #     root_y = self.find(y)
    #     if root_x == root_y:
    #         return False
    #     else:
    #         rank_x = -self.nodes[root_x]
    #         rank_y = -self.nodes[root_y]
    #         if rank_x < rank_y:
    #             self.nodes[root_x] = root_y
    #             self.weight[root_x] = w - self.weight[y] - self.weight[x]
    #         else:
    #             self.nodes[root_y] = root_x
    #             self.weight[root_y] = w - self.weight[x] - self.weight[y]
    #
    #             if rank_x == rank_y:
    #                 self.nodes[root_x] += -1
    #
    #         return True

    # xとyのルートが等しい時: 入力された重みwが正しいかどうかを判定
    # xとyのルートが異なる時: xとyを併合する
    # True: 併合した，False: 何もしなかった，ValueError: 入力された重みに矛盾がある
    def relate(self, x: int, y: int, w: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:  # 入力された重みwに矛盾がないか判定
            # print(x, y, self.weight[x], self.weight[y], w)
            # print(self.get_tree())
            # print(self.weight)
            if self.weight[x] - self.weight[y] == w:
                return False
            raise ValueError
        else:
            rank_x = -self.nodes[root_x]
            rank_y = -self.nodes[root_y]
            if rank_x < rank_y:
                self.nodes[root_x] = root_y
                self.weight[root_x] = w + self.weight[y] - self.weight[x]
            else:
                self.nodes[root_y] = root_x
                self.weight[root_y] = -w + self.weight[x] - self.weight[y]

                if rank_x == rank_y:
                    self.nodes[root_x] += -1
            return True

    # UnionFind木の一覧を返す
    def get_tree(self) -> dict:
        tree = {}
        for i, node in enumerate(self.nodes):
            if node < 0:
                if i not in tree.keys():
                    tree[i] = []
            else:
                if self.find(node) in tree.keys():
                    tree[self.find(node)].append(i)
                else:
                    tree[self.find(node)] = [i]

        return tree


N, M = inpl()
uf = UnionFind(N)
relate = uf.relate
try:
    for i in range(M):
        l, r, d = inpl()
        relate(l - 1, r - 1, d)
    else:
        print('Yes')
except ValueError:
    print('No')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lrd = []

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]


target = lrd[0][0]
a[target] = 0
temp = [target]
t = 0
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if lrd[y][3] == 1:
                continue

            if lrd[y][0] == x:
                t = lrd[y][1]
                d = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                d = a[x] - lrd[y][2]

            lrd[y][3] = 1

            if a[t] == MAX:
                a[t] = d
                next.append(t)
            elif a[t] != d:
                print('No')
                exit()

    if len(next) == 0:
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                check = 1
                target = lrd[i][0]
                break

        if check == 1:
            temp = [target]
            a[target] = 0
            continue
        else:
            break

    temp = [] + list(set(next))

print('Yes')

Submission status: Accepted

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


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

    # 検索
    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 weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    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]


WUF = WeightedUnionFind(N)
for i in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    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:
n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  g[l-1].append([r-1,d])
  g[r-1].append([l-1,-d])
syo = [-1] * n
que = []
for i in range(n):
  if syo[i] != -1:
    continue
  syo[i] = 0
  que.append(i)
  while que:
    x = que.pop()
    for j,jb in g[x]:
      if (syo[j] != syo[x]+jb and syo[j] != -1):
        print("No")
        exit()
      syo[j] = syo[x] + jb
      que.append(j)
    g[x] = []
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque

n, m = list(map(int, input().split()))
paths = {}
for i in range(m):
    l, r, d = list(map(int, input().split()))
    if not l in paths.keys():
        paths[l] = [(r, d)]
    else:
        paths[l].append((r, d))
    if not r in paths.keys():
        paths[r] = [(l, -d)]
    else:
        paths[r].append((l, -d))
      
x = [None]*(n+1)
for i in range(1, n+1):
    if x[i] is None:
        x[i] = 0
        que = deque([i])
        while len(que) > 0:
            j = que.popleft()
            if not j in paths.keys():
                continue
            for k, d in paths[j]:
                if x[k] is None:
                    x[k] = x[j] + d
                    que.append(k)
                elif x[k] != x[j] + d:
                    print('No')
                    exit()
# print(x)
print('Yes')