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:
# -*- coding: utf-8 -*-

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)
        # 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())
uf = WeightedUnionFind(n)
for _ in range(m):
    l,r,d = map(int, input().split())
    if uf.same(l,r):
        if uf.diff(l,r) != d:
            print("No")
            exit()
    else:
        uf.unite(l,r,d)

print("Yes")

Submission status: Accepted

Solution code:
class UnionFind:
    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 is_same(self,x,y):
        return self.find(x)==self.find(y)

    def union(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 diff(self,x,y):
        return self.weight[x] - self.weight[y]


N,M = list(map(int,input().split()))
un = UnionFind(N)

for i in range(M):
    l,r,w = list(map(int,input().split()))
    if un.is_same(l,r):
        diff = un.diff(l,r)
        if diff != w:
            print('No')
            exit()
    else:
        un.union(l,r,w)

print('Yes')

Submission status: Accepted

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

L2R = {i:[] for i in range(N+1)}
R2L = {i:[] for i in range(N+1)}

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

x = [0 for i in range(N+1)]
f = [True for i in range(N+1)]

for i in range(1,N+1):
    if f[i]:
        f[i]=False
        x[i]=i
        que=L2R[i]+R2L[i]
        while len(que)>0:
            tmp = []
            for end,d,begin in que:
                if f[end]:
                    f[end]=False
                    x[end]=d+x[begin]
                    tmp+=L2R[end]+R2L[end]
                elif x[end]!=d+x[begin]:
                    print('No')
                    exit()
            que=tmp
print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    #ret = True
    for elem in G[i]:
        if field[elem[0]] is not None:
            if field[elem[0]] != field[i]+elem[1]:
                return False
            continue
        else:
            field[elem[0]] = field[i]+elem[1]
            ret = dfs(elem[0])
            if not ret:
                return False
    return True

    #q = deque()
    #q.append(i)
    #field[i] = 0
    #while q:
    #    tmp = q.pop()
    #    for elem in G[tmp]:
    #        if field[elem[0]] is not None:
    #            if field[elem[0]] != field[tmp]+elem[1]:
    #                return False
    #            continue
    #        else:
    #            q.append(elem[0])
    #            field[elem[0]] = field[tmp]+elem[1]
    #return True


for i in range(1, N+1):
    if field[i] is None:
        field[i] = 0
        if not dfs(i):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    q = deque()
    q.append(i)
    field[i] = 0
    while q:
        tmp = q.pop()
        for elem in G[tmp]:
            if field[elem[0]] is not None:
                if field[elem[0]] != field[tmp]+elem[1]:
                    return False
                continue
            else:
                q.append(elem[0])
                field[elem[0]] = field[tmp]+elem[1]
    return True


for i in range(1, N+1):
    if field[i] is None:
        if not dfs(i):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
#L = []
#R = []
#D = []
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    # L.append(tmpl)
    # R.append(tmpr)
    # D.append(tmpd)
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    q = deque()
    q.append(i)
    field[i] = 0
    #used = [False]*(N+1)
    #used[i] = True
    while q:
        tmp = q.pop()
        for elem in G[tmp]:
            if field[elem[0]] is not None:
                if field[elem[0]] != field[tmp]+elem[1]:
                    return False
                continue
            else:
                q.append(elem[0])
                field[elem[0]] = field[tmp]+elem[1]

            # if used[elem[0]]:
            #    if field[elem[0]] is not None:
            #        if field[elem[0]] != field[tmp]+elem[1]:
            #            return False
            #    continue
            # q.append(elem[0])
            # if field[elem[0]] == None:
            #    field[elem[0]] = field[tmp]+elem[1]
            #    used[elem[0]] = True
            # else:
            #    if field[elem[0]] != field[tmp]+elem[1]:
            #        return False

    return True


for i in range(1, N+1):
    if field[i] == None:
        if not dfs(i):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def rec(x, n):
    # print(pos)
    if pos[x] is None:
        pos[x] = n
    else:
        if pos[x] == n:
            return True
        else:
            # print(pos[x], n)
            return False

    for nx, d in g[x]:
        if not rec(nx, n + d):
            return False
    else:
        return True

INF = 1 << 30

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

pos = [None for _ in range(N)]

for v in range(N):
    # print(pos)
    if pos[v] is None:
        if not rec(v, 0):
            print('No')
            break
else:
    print('Yes')

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

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

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    if r != rootr:
      # 直接yにつなげる
      dis[rootl] = d - cost(l)
    else:
      # 根につなげる
      dis[rootl] = d - (cost(l) - cost(r))  # d - (dis[l] - dis[r])
    # ここで親を更新
    par[rootl] = r
  else:
    if d != cost(l) - cost(r):
      print("No")
      exit()

print("Yes")

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

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

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  # rootl, rootr = root(l), root(r)
  # 確かめ用
  rootl = root(l)
  rootr = root(r)
  if rootl != rootr:
    if r != rootr:
      # 直接yにつなげる
      dis[rootl] = d - cost(l)
    else:
      # 根につなげる
      dis[rootl] = d - (cost(l) - cost(r)) # (dis[l] - dis[r])
    # ここで親を更新
    par[rootl] = r
  else:
    if d != cost(l) - cost(r):
      print("No")
      exit()

  """
  ちょっとなにがダメなのかわかんないので確かめる
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (dis[l] - dis[r]) # (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
  """
print("Yes")

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

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

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  # rootl, rootr = root(l), root(r)
  # 確かめ用
  rootl = root(l)
  rootr = root(r)
  if rootl != rootr:
    if r != rootr:
      # 直接yにつなげる
      dis[rootl] = d - cost(l)
    else:
      # 根につなげる
      dis[rootl] = d - (dis[l] - dis[r])
    # ここで親を更新
    par[rootl] = r
  else:
    if d != cost(l) - cost(r):
      print("No")
      exit()

  """
  ちょっとなにがダメなのかわかんないので確かめる
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (dis[l] - dis[r]) # (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
  """
print("Yes")

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

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

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

# 確かめ用
def unite(x, y, w):
  rootx = root(x)
  rooty = root(y)
  if rootx != rooty:
    if y != rooty:
      # 直接yにつなげる
      dis[rootx] = w - cost(x)
    else:
      # 根につなげる
      dis[rootx] = w - (dis[x] - dis[y])
    # ここで親を更新
    par[rootx] = y
  else:
    if w != cost(x) - cost(y):
      print("No")
      exit()


for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  # 確かめ用
  a = unite(l, r, d)
  if a is not None:
    if a == False:
      flag = False

  """
  ちょっとなにがダメなのかわかんないので確かめる
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (dis[l] - dis[r]) # (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
  """
print("Yes")

Submission status: Accepted

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

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

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

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])

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

def unite(x, y, w):
  rootx = root(x)
  rooty = root(y)
  if rootx != rooty:
    if y != rooty:
      # 直接yにつなげる
      dist[rootx] = w - direct_cost(x)
    else:
      # 根につなげる
      dist[rootx] = w - (dist[x] - dist[y])
    # ここで親を更新
    par[rootx] = y
  else:
    return w == diff(x, y)

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  a = unite(l, r, d)
  if a is not None:
    if a == False:
      flag = False
  """
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(l)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[r])
    par[rootx] = l
  else:
    if d != diff(l, r):
      flag = False
  """
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    na = list(map(int, input().split()))
    N = na[0]
    M = na[1]
    lrd_list = []
    for i in range(M):
        na = list(map(int, input().split()))
        lrd_list.append((na[0], na[1], na[2]))

    l_list = [None for i in range(N+1)]
    r_list = [None for i in range(N+1)]
    for lrd in lrd_list:
        l = lrd[0]
        r = lrd[1]
        if l_list[l] is None:
            l_list[l] = [lrd]
        else:
            l_list[l].append(lrd)
        if r_list[r] is None:
            r_list[r] = [lrd]
        else:
            r_list[r].append(lrd)

    positions = [None for i in range(N+1)]
    consistent = True
    i = 1
    while consistent and i <= N:
        s = []
        p = 0
        positions[i] = p
        s.append(i)
        while consistent and 0 < len(s):
            j = s.pop()
            p = positions[j]
            if not l_list[j] is None:
                for lrd in l_list[j]:
                    l, r, d = lrd
                    if positions[r] is None:
                        positions[r] = p + d
                        s.append(r)
                    elif positions[r] != p + d:
                        consistent = False
                        break
                if not consistent:
                    break
            if not r_list[j] is None:
                for lrd in r_list[j]:
                    l, r, d = lrd
                    if positions[l] is None:
                        positions[l] = p - d
                        s.append(l)
                    elif positions[l] != p - d:
                        consistent = False
                        break
        while consistent and i <= N and (not positions[i] is None):
            i += 1


    print('Yes' if consistent else 'No')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class WeightedUnionFindTree:
  def __init__(self, n):
    self.par = list(range(n))
    self.rank = [0 for _ in range(n)]
    self.weight = [0 for _ in range(n)]
   
  def root(self, t):
    if t == self.par[t]:
      return t
    # 経路圧縮してみる
    r = self.root(self.par[t])
    self.weight[t] += self.weight[self.par[t]]
    self.par[t] = r
    return r
   
  def rec_weight(self, t):
    if t == self.par[t]:
      return 0
    return self.weight[t] + self.rec_weight(self.par[t])
   
  def same(self, x, y):
    return self.root(x) == self.root(y)
     
  def unite(self, x, y, w):
    rootx = self.root(x)
    rooty = self.root(y)
    if rootx != rooty:
      if y != rooty:
        # 直接yにつなげる
        self.weight[rootx] = w - self.rec_weight(x)
      else:
        # 根につなげる
        self.weight[rootx] = w - (self.weight[x] - self.weight[y])
      # ここで親を更新
      self.par[rootx] = y
    else:
      return w == self.diff(x, y)
 
  def diff(self, x, y):
    return self.rec_weight(x) - self.rec_weight(y)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]


wuft = WeightedUnionFindTree(n+1)
flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  a = wuft.unite(l, r, d)
  if a is not None:
    if a == False:
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(wuft.par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(wuft.weight)]
print()
"""

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

Submission status: Accepted

Solution code:
def dfs(graph, start, visited):
    if visited[start] != -99999:
        return True

    stack = [start]
    visited[start] = 0#初期値を0に設定
    while stack:
        label = stack.pop()
        for nextnode, distance in graph[label]:
            if visited[nextnode] == -99999:#初めて訪れる場所なら座標を設定
                stack.append(nextnode)
                visited[nextnode] = visited[label] + distance
            elif visited[nextnode] != visited[label] + distance:#二回目以降なら一回目と同じかを確認，stackはとらない
                return False
    return True


N, M = (int(i) for i in input().split())

graph = [[] for i in range(N + 1)]#インデックス番号と実際の番号をあわせるためにN+1にする

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    graph[L].append((R, D))
    graph[R].append((L, -1 * D))

visited = [-99999 for i in range(N + 1)]

flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

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

Submission status: Accepted

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

"""
参考：https://www.hamayanhamayan.com/entry/2018/01/28/231916
・深さ優先
・幅優先とほとんど一緒だけど練習用にこっちも書いた。
"""

import sys

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)

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

l_edges = [[] for i in range(N)]
r_edges = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    l_edges[l-1].append((r-1, d))
    r_edges[r-1].append((l-1, d))

# 訪問済メモ
visited = [0] * N

def dfs(cur):
    visited[cur] = 1
    # 左から見た右側を確認
    for r, d in l_edges[cur]:
        # 訪問済なら矛盾がないか検証する
        if visited[r]:
            if pos[r] - pos[cur] != d:
                print('No')
                exit()
        # 未訪問なら今回の情報を記録する
        else:
            visited[r] = 1
            pos[r] = pos[cur] + d
            # 確認した位置を次の現在位置として見に行く
            dfs(r)
    # 右から見た左側を確認
    for l, d in r_edges[cur]:
        if visited[l]:
            if pos[cur] - pos[l] != d:
                print('No')
                exit()
        else:
            visited[l] = 1
            pos[l] = pos[cur] - d
            dfs(l)

for i in range(N):
    # 訪問済(確認済)でなければ走破しに行く
    if not visited[i]:
        # この開始位置を基準とした相対位置を記録する
        pos = {i: 0}
        dfs(i)
        pos = {}
# 最後まで矛盾がなければOK
print('Yes')

Submission status: Accepted

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

"""
参考：https://www.hamayanhamayan.com/entry/2018/01/28/231916
・幅優先
・辺の情報の持たせ方を工夫して、辺のループを余計に回さないようにする。
"""

from collections import deque

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

l_edges = [[] for i in range(N)]
r_edges = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    l_edges[l-1].append((r-1, d))
    r_edges[r-1].append((l-1, d))

# 訪問済メモ
visited = [0] * N

def bfs(start):
    # この開始位置を基準とした相対位置を記録する
    pos = {start: 0}
    que = deque()
    que.append(start)
    visited[start] = 1
    while len(que) != 0:
        cur = que.popleft()
        # 左から見た右側を確認
        for r, d in l_edges[cur]:
            # 訪問済なら矛盾がないか検証する
            if visited[r]:
                if pos[r] - pos[cur] != d:
                    print('No')
                    exit()
            # 未訪問なら今回の情報を記録する
            else:
                visited[r] = 1
                pos[r] = pos[cur] + d
                # 次回以降、開始位置として使うのでキューに詰める
                que.append(r)
        # 右から見た左側を確認
        for l, d in r_edges[cur]:
            if visited[l]:
                if pos[cur] - pos[l] != d:
                    print('No')
                    exit()
            else:
                visited[l] = 1
                pos[l] = pos[cur] - d
                que.append(l)

for i in range(N):
    # 訪問済(確認済)でなければ走破しに行く
    if not visited[i]:
        bfs(i)
# 最後まで矛盾がなければOK
print('Yes')

Submission status: Accepted

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

"""
参考：http://hamko.hatenadiary.jp/entry/2018/01/30/210057
　　　http://at274.hatenablog.com/entry/2018/02/03/140504
・重み付きUnion-Find木
"""

import sys
def input(): return sys.stdin.readline().strip()

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 i in range(M):
    x, y, w = map(int, input().split())
    # 同じ集合に属する場合
    if wuf.same(x, y):
        # 記録された距離と今回の情報に矛盾がないか確認
        if wuf.diff(x, y) != w:
            print('No')
            exit()
    wuf.union(x, y, w)
# 全部無矛盾で木が構築できればOK
print('Yes')

Submission status: Accepted

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

"""
参考：http://hamko.hatenadiary.jp/entry/2018/01/30/210057
　　　http://at274.hatenablog.com/entry/2018/02/03/140504
・重み付きUnion-Find木
"""

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 i in range(M):
    x, y, w = map(int, input().split())
    # 同じ集合に属する場合は
    if wuf.same(x, y):
        # 記録された距離と今回の情報に矛盾がないか確認
        if wuf.diff(x, y) != w:
            print('No')
            exit()
    wuf.union(x, y, w)
# 全部無矛盾で木が構築できればOK
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 d != wuf.diff(l, r):
            print('No')
            break
    else:
        wuf.union(l, r, d)
else:
    print('Yes')

Submission status: Accepted

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

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            if w != self.diff(x, y):
                print("No")
                exit()

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

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

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


N, M = map(int, input().split())
w_union_find = WeightedUnionFind(N)
for i in range(M):
    l, r, d = map(int, input().split())
    w_union_find.union(l, r, d)
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]


import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
lrd = []
for i in range(M):
    l, r, d = map(int, input().split())
    lrd.append([l, r, d])
w_union_find = WeightedUnionFind(N)
for i in range(M):
    l, r, d = lrd[i]
    w_union_find.union(l, r, d)
print("Yes")

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