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


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

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

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

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

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

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

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


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

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

print('Yes')

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        self.potential=[0]*(n+1)
 
    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            r = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            self.root[x]=r
            return self.root[x]
 
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y, d):
        d+=self.potential[x]-self.potential[y]
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.potential[y]=d
 
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
 
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def dist(self,x,y):
        if self.isSameGroup(x,y):
            return self.potential[y]-self.potential[x]
        else: return -10**10

n,m=map(int,input().split())
if m==0:
  print('Yes')
else:
  t=UnionFind(n)
  arr=[list(map(int,input().split())) for _ in range(m)]
  for l,r,d in arr:
    if t.isSameGroup(l,r) and t.dist(l,r)!=d:
      print('No')
      break
    t.Unite(l,r,d)
  else:
    print('Yes')

Submission status: Accepted

Solution code:
from sys import exit, stdin

class WeightedUnionFind:

    def __init__(self, n=1, sum_unity=0):

        self.par = [i for i in range(n)]

        self.rank = [0]*n

        self.diff_weight = [sum_unity]*n

    

    def find_root(self, x):

        if self.par[x] == x:

            return x

        else:

            y = self.find_root(self.par[x])

            self.diff_weight[x] += self.diff_weight[self.par[x]]

            self.par[x] = y

            return y

    def merge(self, x, y, w):

        rx, ry = self.find_root(x), self.find_root(y)

        if self.rank[rx] < self.rank[ry]:

            self.par[rx] = ry

            self.diff_weight[rx] = w - self.diff_weight[x] + self.diff_weight[y]

        else:

            self.par[ry] = rx

            self.diff_weight[ry] = -w - self.diff_weight[y] + self.diff_weight[x]

            if self.rank[rx] == self.rank[ry]:

                self.rank[rx] += 1

    def issame(self, x, y):

        return self.find_root(x) == self.find_root(y)

    def diff(self, x, y):

        return self.diff_weight[x] -  self.diff_weight[y]

N, M = [int(_) for _ in stdin.readline().rstrip().split()]

wuf = WeightedUnionFind(N)

for i in range(M):

    l, r, d = [int(_) for _ in stdin.readline().rstrip().split()]

    l -= 1

    r -= 1

    if wuf.issame(l, r):

        diff = wuf.diff(l, r)

        if diff != d:

            print("No")

            exit()

    else:

        wuf.merge(l, r, d)

print("Yes")

Submission status: Accepted

Solution code:
from sys import exit, stdin

class WeightedUnionFind:
    def __init__(self, n=1, sum_unity=0):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.diff_weight = [sum_unity]*n

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


    def merge(self, x, y, w):
        rx, ry = self.find_root(x), self.find_root(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.diff_weight[rx] = w - self.diff_weight[x] + self.diff_weight[y]
        else:
            self.par[ry] = rx
            self.diff_weight[ry] = -w - self.diff_weight[y] + self.diff_weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1


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


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

N, M = [int(_) for _ in stdin.readline().rstrip().split()]

wuf = WeightedUnionFind(N)
for i in range(M):
    l, r, d = [int(_) for _ in stdin.readline().rstrip().split()]
    l -= 1
    r -= 1
    if wuf.issame(l, r):
        diff = wuf.diff(l, r)
        if diff != d:
            print("No")
            exit()
    else:
        wuf.merge(l, r, d)
print("Yes")

Submission status: Accepted

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

def dfs(v,p,pos):
  q = [(v,p)]
  while q:
    cv,cp = q.pop()
    if pos[cv] != None:
      continue
    pos[cv] = cp
    for i,d in l[cv]:
      if pos[i] == None:
        q.append((i,cp+d))
  return

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

Submission status: 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
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')

Submission status: Accepted

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N, M = (int(_) for _ in input().split())
    L = []
    R = []
    D = []
    for i in range(M):
        s1,s2,s3 = (int(_) for _ in input().split())
        L.append(s1)
        R.append(s2)
        D.append(s3)
    if M ==0:
        print('Yes')
        return
    adj = [[] for _ in range(N)]
    for i in range(M):
        adj[L[i]-1].append([R[i]-1,D[i]])
        adj[R[i]-1].append([L[i]-1,-1*D[i]])

    dist = [None for _ in range(N)]
    for i in range(N):
        if dist[i] is not None:
            continue
        stack = [i]
        dist[i] = 0
        while stack:
            v=stack.pop()
            for to,cost in adj[v]:
                if dist[to] is None:
                    stack.append(to)
                    dist[to] = dist[v]+cost
                elif dist[to] != dist[v] +cost:
                    print('No')
                    return
        
    print('Yes')
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        self.potential=[0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            r = self.Find_Root(self.root[x])
            self.potential[x] += self.potential[self.root[x]]
            self.root[x]=r
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y, d):
        d+=self.potential[x]-self.potential[y]
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.potential[y]=d

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.potential[x]=-d
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def dist(self,x,y):
        if self.isSameGroup(x,y):
            return self.potential[y]-self.potential[x]
        else: return -10**10



INF=10**10

N,M=map(int,input().split())
if M==0: print("Yes"),sys.exit()

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

for i in range(M):
    l,r,d=dist[i]
    if tree.isSameGroup(l,r) and tree.dist(l,r)!=d: print("No"),sys.exit()
    tree.Unite(l,r,d)

print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N, M =map(int, input().split())
G=[[]for i in range(N+1)]
for i in range(M):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,-c),

d = [10**9]*(N+1)
flag = True
def f(v, u):
    global flag
    if not flag:
        d[v] = 0
        return 0
    else:
        d[v] = u
        for t, c in G[v] :
            if d[t] == 10**9:
                f(t, u+c)
            else:
                if d[t] != u+c:
                    flag = False
                    
for i in range(1, N+1):
    if d[i] == 10**9:
        f(i, 0)
if flag:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

INF = float("inf")
# 人iまでの距離
cost = [INF] * (n+1)
# 人iからjまでの距離がd
edges = [[] for _ in range(n+1)]
for _ in range(m):
  l, r, d = map(int, input().split())
  # l->rとr->lの辺を保存
  edges[l].append((r, d))
  edges[r].append((l, -d))
  
  
# ある人、a->bまでの距離が引数、人iまでの距離がcで矛盾がないかを戻す
# dfsだと思うがよくあるif(終了条件)みたいな形ではない
def solve(i, c):
  # ある人までの距離が未決定の場合
  if cost[i] == INF:
    cost[i] = c
    # 「人i-> jがdの距離」の情報を全て見て回り矛盾が生じないか確認
    for j, d in edges[i]:
      if solve(j, c + d) == False:
        return False
  
  return cost[i] == c

ans = "Yes"

for i in range(1, n+1):
  if cost[i] == INF and solve(i, 0) == False:
    ans = "No"
    
    
print(ans)

Submission status: Accepted

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

LIMIT = 10 ** 9

class UnionFind():
    def __init__(self, N):
        self.nodes = [i for i in range(N)]
        self.distance = [0 for _ in range(N)]

    def root(self, x):
        if x != self.nodes[x]:
            root, distance = self.root(self.nodes[x])
            if self.nodes[x] != root:
                self.distance[x] += distance
                self.nodes[x] = root
        return self.nodes[x], self.distance[x]

    def same(self, x, y):
        x_root, _ = self.root(x)
        y_root, _ = self.root(y)
        return x_root == y_root

    # unite(L, R, D)
    def unite(self, x, y, distance):
        if self.same(x, y):
            return self.distance[y] - self.distance[x] == distance
        x_root, _ = self.root(x)
        y_root, _ = self.root(y)
        self.distance[y_root] = self.distance[x] + distance - self.distance[y]
        self.nodes[y_root] = x_root
        return True

is_correct = True
uf = UnionFind(N)
for _ in range(M):
    l, r, d = map(int, input().split())
    is_valid = uf.unite(l-1, r-1, d)
    if not is_valid:
        is_correct = False
        break

distance_dict = {}
for group, distance in zip(uf.nodes, uf.distance):
    if group in distance_dict:
        distance_dict[group]["max"] = max(distance_dict[group]["max"], distance)
        distance_dict[group]["min"] = min(distance_dict[group]["min"], distance)
    else:
        distance_dict[group] = {
            "max": distance,
            "min": distance,
        }

for distances in distance_dict.values():
    if distances["max"] - distances["min"] > LIMIT:
        is_correct = False
        break
print("Yes" if is_correct else "No")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
par = [-1]*n
wei = [0]*n

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

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


def unite(x,y,w):
  w+=wei[x]-wei[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
    wei[y]=w
    return True

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

def size(x):
    return -par[find(x)]

def diff(x,y):
    return weight(y)-weight(x)
flag=1
for i in range(m):
  l,r,d=map(int,input().split())
  if same(l-1,r-1):
    if d!=diff(l-1,r-1):
      flag=0
  else:
    unite(l-1,r-1,d)
print("No" if flag==0 else "Yes")

Submission status: Accepted

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

# uf treeの亜種


N,M = map(int,input().split())
root = list(range(N+1))
pos = [0] * (N+1) # rootからの相対座標
depth = [0] * (N+1)

def find_root(x):
  # root および 相対座標 を返す
  y = root[x]
  if x == y:
    return y,0
  z,p = find_root(y)
  root[x] = z
  pos[x] += p
  return z,pos[x]

def merge(x,y,d):
  # y = x + dという位置関係
  rx,px = find_root(x)
  ry,py = find_root(y)
  if rx == ry:
    return (py == px + d)
  # pos[ry] + py = pos[rx] + px + d
  # pos[ry] = pos[rx] + (px-py+d)
  dd = px-py+d
  if depth[rx] > depth[ry]:
    root[ry] = rx
    pos[ry] = dd
  else:
    root[rx] = ry
    pos[rx] = -dd
    depth[ry] += 1
  return True

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():

    class WeightedUnionFind():
        def __init__(self, n):
            self.nodes = [-1 for _ in range(n)]
            self.weight = [0] * n

        def get_root(self, x):
            if self.nodes[x] < 0:
                return x
            else:
                y = self.get_root(self.nodes[x])
                self.weight[x] += self.weight[self.nodes[x]]
                self.nodes[x] = y
                return y

        def unite(self, x, y, w):
            w += self.weight[x]-self.weight[y]
            root_x = self.get_root(x)
            root_y = self.get_root(y)
            if root_x != root_y:
                # 大きい木の方につないだほうが計算量が減る
                if self.nodes[root_x] > self.nodes[root_y]:
                    root_x, root_y = root_y, root_x
                    w *= -1
                self.nodes[root_x] += self.nodes[root_y]
                self.nodes[root_y] = root_x
                self.weight[root_y] = w

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

        def same(self, x, y):
            return get_root(x) == get_root(y)
    N, M = MI()
    uf = WeightedUnionFind(N)
    get_root, unite, nodes, diff, same = uf.get_root, uf.unite, uf.nodes, uf.diff, uf.same
    for _ in range(M):
        l, r, d = MI_()
        d += 1
        if same(l, r) and diff(l, r) != d:
            print("No")
            exit()
        else:
            unite(l, r, d)
    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():

    class WeightedUnionFind():
        def __init__(self, n):
            self.nodes = [-1 for _ in range(n)]
            self.weight = [0] * n

        def get_root(self, x):
            if self.nodes[x] < 0:
                return x
            else:
                y = self.get_root(self.nodes[x])
                self.weight[x] += self.weight[self.nodes[x]]
                self.nodes[x] = y
                return y

        def unite(self, x, y, w):
            w += self.weight[x]-self.weight[y]
            root_x = self.get_root(x)
            root_y = self.get_root(y)
            if root_x != root_y:
                # 大きい木の方につないだほうが計算量が減る
                if self.nodes[root_x] > self.nodes[root_y]:
                    root_x, root_y = root_y, root_x
                    w *= -1
                self.nodes[root_x] += self.nodes[root_y]
                self.nodes[root_y] = root_x
                self.weight[root_y] = w

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

        def same(self, x, y):
            return get_root(x) == get_root(y)
    N, M = MI()
    edge = [[] for _ in range(N)]
    uf = WeightedUnionFind(N)
    get_root, unite, nodes, diff, same = uf.get_root, uf.unite, uf.nodes, uf.diff, uf.same
    distanse = [0] * N
    distanse[0] = 0
    rev_edge = [[]for _ in range(N)]
    for _ in range(M):
        l, r, d = MI_()
        d += 1
        edge[l].append((r, d))
        if same(l, r) and diff(l, r) != d:
            print("No")
            exit()
        else:
            unite(l, r, d)

    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)
weight = [0] * (n + 1)

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

def union(x, y, w):
    rx = find(x)
    ry = find(y)
    if rank[rx] < rank[ry]:
        parent[rx] = ry
        weight[rx] = w - weight[x] + weight[y]
    else:
        parent[ry] = rx
        weight[ry] = -w - weight[y] + weight[x]
        if rank[rx] == rank[ry]:
            rank[rx] += 1

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

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

ans = "Yes"
for i in range(m):
    l, r, d = map(int, input().split())
    if same_check(l, r):
        if diff(l, r) != d:
            ans = "No"
            break
    else:
        union(l, r, d)
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
checked=set()
from collections import defaultdict
branch=defaultdict(dict)
flag=True
for i in range(M):
    L,R,D=map(int,input().split())
    branch[L-1][R-1]=D
    branch[R-1][L-1]=-1*D
for i in range(N):
    if i in checked:
        continue
    if not flag:
        break
    dist=dict()
    dist[i]=0
    check={i}
    while len(check)>0:
        now=check.pop()
        checked|={now}
        for nex,d in branch[now].items():
            if nex not in dist.keys():
                dist[nex]=dist[now]+d
                check|={nex}
            elif dist[nex]!=dist[now]+d:
                flag=False
                check=set()
                break
if flag:
    print('Yes')
else:
    print('No')

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
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')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c = list(range(n+1)) #色
a = [] #色ごとのリスト
for i in range(n+1):
  a.append([i])
b = [1]*(n+1) #色ごとの頂点数
p = [0]*(n+1) #位置
#print(a)
for i in range(m):
  x,y,d = map(int,input().split())
  u = c[x]
  v = c[y]
  if b[u] < b[v]:
    x,y = y,x
    u,v = v,u
    d = -d
  if u != v:
    l = d + p[x] - p[y]
    for t in a[v]:
      c[t] = u
      p[t] += l
    a[u] += a[v]
    a[v] = []
    b[u] += b[v]
    b[v] = 0
  else:
    if not p[y]-p[x] == d:
      #print(p)
      print("No")
      quit()
print("Yes")

Submission status: Accepted

Solution code:
N,M = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(M) ]

up = [ set([]) for i in range(N)]
dw = [ set([]) for i in range(N)]

for l,r,d in li:
  dw[l-1].add(r-1)
  up[r-1].add(l-1)

S = []
for n in range(N):
  if ( len(up[n])==0 ):
    S.append(n)
L = []
for i in range(N+M):

  if ( len(S)==0 ):
    break
  n = S.pop()
  L.append(n)
  for r in dw[n]:
    up[r].discard(n)
    if ( len(up[r]) == 0 ):
      S.append(r)
  dw[n]=set()

BREAK=False
if (sum([len(s) for s in up])>0):
    BREAK=True

dwl = [ set([]) for i in range(N)]
for l,r,d in li:
  dwl[l-1].add((r-1,d))

dis = [-1]*N

for n in L:
  if (BREAK):
    break
  if (dis[n]==-1):
    dis[n]=0
  for r,d in dwl[n]:
    if (dis[r]==-1):
        dis[r]=dis[n]+d
    else:
        if not (dis[r]==dis[n]+d):
            BREAK=True
            break
if (BREAK):
    print ("No")
else:
    print ("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict

N,M = map(int,input().split(" "))
G = defaultdict(lambda:[])
D = defaultdict(lambda:-1)
E = defaultdict(lambda:0)
for i in range(M):
    l,r,d = map(int,input().split(" "))
    l -= 1
    r -= 1
    G[l].append((r,d))
    E[r] = 1
for i in range(N):
    if E[i]:
        continue
        #   深さ優先探索で探索される予定のやつをはじく
    s = [i]
    #   深さ優先探索
    while len(s):
        l = s.pop()
        for r,d in G[l]:
            if D[r] != -1:
                continue
                #   ここで弾くと計算量が減る？わからん
            D[r] = D[l] + d
            s.append(r)
for l in range(N):
    for r,d in G[l]:
        if D[l] + d == D[r]:
            continue
        print("No")
        exit()

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 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):
        if self.same(x, y):
            return self.weight[x] - self.weight[y]
n, m=map(int, input().split())
U=WeightedUnionFind(n)
def C(U):
    for i in range(m):
        l, r, d = map(int, input().split())
        if U.same(l-1, r-1):
            if U.diff(l-1, r-1)!=d:
                return False
        else:
            U.union(l-1, r-1, d)
    return True
if C(U):
    print('Yes')
else:
    print('No')