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:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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)
        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 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=MI()
wuf=WeightedUnionfind(n)
for i in range(m):
    l,r,d=MI()
    #print(l,r,d,end=" ")
    #print(wuf.same(l,r))
    if wuf.same(l,r):
        #print(wuf.diff(l,r))
        if wuf.diff(l,r)!=d:
            print("No")
            sys.exit()
    else:
        wuf.union(l,r,d)
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
graph = [[] for i in range(N)]
for _ in range(M):
  l,r,d = map(int,input().split())
  graph[l-1].append((r-1,d))
  graph[r-1].append((l-1,-d))

q = deque([i for i in range(N)])
pos = [None for i in range(N)]
while q:
  x = q.popleft()
  if pos[x] == None:
    pos[x] = 0
  for y,d in graph[x]:
    if pos[y] == None:
      pos[y] = pos[x] + d
      q.appendleft(y)
      continue
    if pos[y] != pos[x] + d:
      print("No")
      exit()

print("Yes")

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N,M = getNM()
dist = [[] for i in range(N)]
for i in range(M):
    a, b, c = getNM()
    dist[a - 1].append((b - 1, c))
    dist[b - 1].append((a - 1, -c))

pos = deque([i for i in range(N)])
point = [float('inf')] * N

while len(pos) > 0:
    now = pos.popleft()
    if point[now] == float('inf'):
        point[now] = 0
    for next, dis in dist[now]:
        if point[next] == float('inf'):
            point[next] = point[now] + dis
            pos.appendleft(next)
            continue
        if point[next] != point[now] + dis:
            print("No")
            exit()

print("Yes")

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N,M = getNM()
graph = [[] for i in range(N)]
for _ in range(M):
  l,r,d = getNM()
  graph[l-1].append((r-1,d))
  graph[r-1].append((l-1,-d))

q = deque([i for i in range(N)])
pos = [None for i in range(N)]
while q:
  x = q.popleft()
  if pos[x] == None:
    pos[x] = 0
  for y,d in graph[x]:
    if pos[y] == None:
      pos[y] = pos[x] + d
      q.appendleft(y)
      continue
    if pos[y] != pos[x] + d:
      print("No")
      exit()

print("Yes")

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    """
    https://qiita.com/drken/items/4a7869c5e304883f539b#3-3-dfs-%E3%81%AE%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%AE%9F%E8%A3%85
    cf. https://atcoder.jp/contests/abc138/submissions/13273052
    """
    
    from collections import deque
    
    
    N, M = map(int, input().split())  # 頂点数，辺数
    # グラフ入力受取 (ここでは無向グラフを想定)
    G = [[] for _ in range(N)]


    for i in range(M):
        l, r,d = map(int, input().split())
        l-=1
        r-=1
        G[l].append((r,d))
        G[r].append((l,-d))
    
    seen = [False]*N
    ans = [0]*N
    
    
    def dfs(G, v):
    
        # (根の親番号が必要なときは-1とする)
    
        seen[v] = True
        stack = deque([v])
        while stack:
            v = stack.pop()
            for next_v,cost in G[v]:
                if not seen[next_v]:
                    ans[next_v] =ans[v]+cost
                else:
                    if ans[next_v] !=ans[v]+cost:
                        return 'No'
                    else: continue

                seen[next_v] = True
                stack.append(next_v)
    
    
    def main():
        for i in range(N):
            if not seen[i]:
                if dfs(G,i)=='No':
                    return 'No'
                    break
                else:
                    continue
        return 'Yes'
    print(main())
    
    
resolve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  edge[l].append((r,d))
  edge[r].append((l,-d))
ans=[10**20]*n
inf=10**20
for i in range(n):
  if ans[i]!=inf:continue
  stack=[i]
  visited={i}
  ans[i]=0
  for node in stack:
    for mode,d in edge[node]:
      if ans[node]+d!=ans[mode]!=inf:exit(print("No")) #ans[node]+d!=ans[mode] and ans[mode]!=inf
      if mode in visited:continue
      visited.add(mode)
      stack.append(mode)
      if ans[mode]==inf:
        ans[mode]=ans[node]+d
        #if ans[node]+d!=ans[mode]:exit(print("No"))
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque

def dfs(s):
    stack = deque([s])
    dist[s] = 0
    while stack:
        v = stack.pop()
        for d, u in E[v]:
            if dist[u] is None:
                dist[u] = dist[v] + d
                stack.append(u)
            else:
                if dist[u] != dist[v] + d:
                    return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, input().split())
    E[l-1].append((d, r - 1))
    E[r-1].append((-d, l - 1))
dist = [None] * N
for i in range(N):
    if dist[i] is not None:
        continue
    if not dfs(i):
        print('No')
        break
else:
    print('Yes')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
vertices = {i: [] for i in range(n)}
for _ in range(m):
    l, r, d = map(int, input().split())
    vertices[l - 1].append((r - 1, d))
    vertices[r - 1].append((l - 1, -d))


def answer():
    x = [None] * n

    for i in range(n):
        if x[i] is not None:
            continue
        x[i] = 0
        queue = [i]

        while queue:
            i0 = queue.pop()
            for i1, d in vertices[i0]:
                # print(i0, i1, x[i0], x[i1], d)
                if x[i1] is None:
                    x[i1] = x[i0] + d
                    queue.append(i1)
                elif x[i1] != x[i0] + d:
                    return False

    return True


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

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
inf = pow(10, 10)

n, m = map(int, input().split())
a = [inf] * n

edge = [[] for i in range(n)]

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

"""
# BFS解放
flag = True
dist = [inf] * n
for i in range(n):
    if not flag: break
    if dist[i] == inf: # 偽の場合、連結で既に訪れている
        dist[i] = 0
        dq = deque([i])
        while dq:
            now = dq.popleft()
            for e in edge[now]:
                nnode, d = e
                if dist[nnode] == inf:
                    dist[nnode] = dist[now] + d
                    dq.append(nnode)
                else:
                    if dist[nnode] != dist[now] + d:
                        flag = False
                        break
if flag:
    print('Yes')
else:
    print('No')
"""

# DFS解法
dist = [inf]*n
def dfs(i, totald = 0):
    if dist[i] < inf:
        if dist[i] == totald:
            return True
        else:
            return False
    dist[i] = totald
    for e in edge[i]:
        nnode, d = e
        if not dfs(nnode, totald+d):
            return False
    return True


f = True
for i in range(n):
    if dist[i] == inf:
        if not dfs(i, 0):
            f = False
            break
if f:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
inf = pow(10, 10)

n, m = map(int, input().split())
a = [inf] * n

edge = [[] for i in range(n)]

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

flag = True
dist = [inf] * n
for i in range(n):
    if not flag: break
    if dist[i] == inf:
        dist[i] = 0
        dq = deque([i])
        while dq:
            now = dq.popleft()
            for e in edge[now]:
                nnode, d = e
                if dist[nnode] == inf:
                    dist[nnode] = dist[now] + d
                    dq.append(nnode)
                else:
                    if dist[nnode] != dist[now] + d:
                        flag = False
                        break
if flag:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

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

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            y = self.find(self.parents[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[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.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.parents[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 main():
    N, M = map(int, readline().rstrip().split())    
    uf = WeightedUnionFind(N)

    for _ in range(M):
        l, r, d = map(int, readline().rstrip().split())
        l -= 1
        r -= 1
        if uf.same(l, r):
            if uf.diff(l, r) != d:
                print('No')
                return

        uf.union(l, r, d)
    
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            y = self.find(self.parents[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[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.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.parents[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 main():
    N, M = map(int, readline().rstrip().split())    
    uf = WeightedUnionFind(N)

    for _ in range(M):
        l, r, d = map(int, readline().rstrip().split())
        l -= 1
        r -= 1
        if uf.same(l, r):
            if uf.diff(l, r) != d:
                print('No')
                return

        uf.union(l, r, d)
    
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            y = self.find(self.parents[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = y
            #self.parents[x] = self.find(self.parents[x])
            return y
            #return self.parents[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.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.parents[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 main():
    N, M = map(int, readline().rstrip().split())    
    uf = WeightedUnionFind(N)

    for _ in range(M):
        l, r, d = map(int, readline().rstrip().split())
        l -= 1
        r -= 1
        if uf.same(l, r):
            if uf.diff(l, r) != d:
                print('No')
                return

        uf.union(l, r, d)
    
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    # 検索
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            y = self.find(self.parents[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[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.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.parents[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 main():
    N, M = map(int, readline().rstrip().split())    
    uf = WeightedUnionFind(N)

    for _ in range(M):
        l, r, d = map(int, readline().rstrip().split())
        l -= 1
        r -= 1
        if uf.same(l, r):
            if uf.diff(l, r) != d:
                print('No')
                return

        uf.union(l, r, d)
    
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

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

pos = {}

def bfs(cur, pre, p):
    stack = deque([(cur, pre, p)])
    while stack:
        cur, pre, p = stack.popleft()
        if cur in pos:
            if p != pos[cur]:
                print('No')
                sys.exit()
        else:
            pos[cur] = p

            for e, d in E[cur]:
                if e != pre:
                    stack.append([e, cur, p + d])

for i in range(n):
    if i in pos:
        continue
    bfs(i, -1, 0)

print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    G[l].append([r, d])
    G[r].append([l, -d])
INF = float('inf')
dist = [INF]*N
seen = [False]*N
q = deque([])
for s in range(N):
    if dist[s] != INF:
        continue
    q.append([s,0])
    while len(q) != 0:
        p = q.popleft()
        if seen[p[0]] and dist[p[0]] != p[1]:
            print('No')
            exit()
        elif seen[p[0]] and dist[p[0]] == p[1]:
            continue
        else:
            dist[p[0]] = p[1]
            seen[p[0]] = True
            for np in G[p[0]]:
                q.append([np[0], p[1] + np[1]])
print('Yes')

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,M = IL()
graph = [[] for i in range(N)]
for _ in range(M):
  l,r,d = IL()
  graph[l-1].append((r-1,d))
  graph[r-1].append((l-1,-d))
  
q = deque([i for i in range(N)])
pos = [None for i in range(N)]
while q:
  x = q.popleft()
  if pos[x] == None:
    pos[x] = 0
  for y,d in graph[x]:
    if pos[y] == None:
      pos[y] = pos[x] + d
      q.appendleft(y)
      continue
    if pos[y] != pos[x] + d:
      print("No")
      exit()

print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            r = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r
    def GetWeight(self, x):
        self.Find_Root(x)
        return self.weight[x]
    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False
        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        self.root[y] = x
        self.weight[y] = w
        return True
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    def Diff(self, x, y):
        return self.GetWeight(y) - self.GetWeight(x)

N, M = map(int, input().split())
uf = UnionFind(N+1)
for _ in range(M):
    l, r, d = map(int, input().split())
    if not uf.isSameGroup(l, r):
        uf.Unite(l, r, d)
    else:
        if uf.Diff(l, r) != d:
            print('No')
            exit()

print('Yes')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(m)]
g=[[] for _ in range(n)]
for l,r,d in lrd:
  g[l-1].append([d,r-1])
  g[r-1].append([-d,l-1])

no_seen=set(range(n))
inf=float('inf')
dst=[inf]*n
while no_seen:
  todo=[[0,no_seen.pop()]]
  #print(todo)
  while todo:
    d,t=todo.pop()
    no_seen.discard(t)
    l=g[t]
    for di,ti in l:
      if dst[ti]!=inf and dst[ti]!=d+di:
        print('No')
        exit()
      elif dst[ti]!=inf and dst[ti]==d+di:
        pass
      else:
        todo.append([d+di,ti])
        dst[ti]=d+di

print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

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

max_int = 10 ** 10
point = [None for _ in range(n)]

for v in range(n):
    Q = deque()
    if point[v] is not None:
        continue
    Q.extend(graph[v])
    while Q:
        next_v, v, d = Q.popleft()
        if point[v] is None:
            point[v] = 0
        if point[next_v] is not None:
            if point[next_v] != point[v] + d:
                print('No')
                exit()
            else:
                continue
        point[next_v] = point[v] + d
        Q.extend(graph[next_v])
print('Yes')

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    LRD = [list(map(int, input().split())) for _ in range(M)]
    adj_list = [[] for _ in range(N)]
    for lrd in LRD:
        l, r, d = lrd
        adj_list[l-1].append((l-1, r-1, d))
        adj_list[r-1].append((r-1, l-1, -d))
    
    X = [None]*N
    import collections

    for i in range(N):
        if X[i] is not None:
            continue
        q = collections.deque(adj_list[i])
        X[i] = 0
        while q:
            src, nxt, d = q.pop()
            if X[nxt] is not None:
                if X[nxt] != X[src] + d:
                    print("No")
                    return
            else:
                X[nxt] = X[src] + d
                q.extend(adj_list[nxt])
    print("Yes")

    


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys
from typing import List, Optional

sys.setrecursionlimit(1000000)

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

g = [[] for _ in range(N)]

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


def ok(cur: int, ds: int, dists: List[Optional[int]]) -> bool:
    dists[cur] = ds

    flag = True
    for nx, d in g[cur]:
        if dists[nx] != None:
            flag &= dists[nx] - dists[cur] == d
        elif flag:
            flag &= ok(nx, ds + d, dists)

    return flag


dists = [None] * N
ans = True
for i in range(N):
    if ans and dists[i] == None:
        ans &= ok(i, 0, dists)

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