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:
n,m = map(int, input().split())

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

from collections import defaultdict
V = defaultdict(list)
 
for _ in range(m):
    a, b,c = map(int, input().split())
    V[a].append([b,c])
    V[b].append([a,-c])

inf  = float("inf") 
dist = [inf]*(n+1)

def dfs(source):
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b[0]]!=inf:
                if dist[b[0]] != dist[a] +b[1]:
                    print("No")
                    exit()
            else:
                dist[b[0]] = dist[a] + b[1]
                q.append(b[0])

for i in range(n):
    if dist[i] ==inf:
        dfs(i)

print("Yes")

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)

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

    visited = [False] * (n + 1)

    for x in range(1, n + 1):
        costs = dict()
        if not visited[x]:
            costs[x] = 0
            que = deque()
            que.append((x, 0))
            while que:
                u, cost = que.popleft()
                visited[u] = True
                while edge[u]:
                    v, w = edge[u].pop()
                    if v in costs:
                        if costs[v] != cost + w:
                            print("No")
                            sys.exit()
                    costs[v] = cost + w
                    que.append((v, cost + w))

    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    li, ri, di = map(int, input().split())
    li, ri = li-1, ri-1
    edges[li].append((ri, di))
    edges[ri].append((li, -di))

coordinate = [None for i in range(n)]
for i in range(n):
    if coordinate[i] == None:
        coordinate[i] = 0
    else:
        continue
    nodes = [i]
    while nodes != []:
        next_nodes = []
        for node in nodes:
            edge = edges[node]
            start = coordinate[node]
            for end, dist in edge:
                if coordinate[end] == None:
                    coordinate[end] = start + dist
                    next_nodes.append(end)
                else:
                    if coordinate[end] != start + dist:
                        print('No')
                        exit()
        nodes = next_nodes[:]
print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

n,m = map(int,input().split())
G = [[] for _ in range(n)]
INF = float("INF")
pos = [INF]*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))

def dfs(now):
    for nxt,d in G[now]:
        if pos[nxt] == INF:
            pos[nxt] = pos[now]+d
            dfs(nxt)
        elif pos[nxt] != pos[now]+d:
            print("No")
            exit()

for i in range(n):
    if pos[i] == INF:
        pos[i] = 0
        dfs(i)
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()))


from collections import defaultdict, deque, Counter
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

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)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
def solve():
    n, m = getList()
    uf = WeightedUnionFind(n+1)
    for i in range(m):
        l, r, d = getList()
        if uf.same(l, r):
            if abs(uf.weight[l] - uf.weight[r]) != d:
                print("No")
                return
        else:
            uf.union(l, r, d)
    print("Yes")
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

def main():
    N, M = LI()
    if M == 0:
        print("Yes")
        return

    G = [[] for _ in range(N)]
    for i in range(M):
        l, r, d = LI()
        l -= 1
        r -= 1
        G[l].append((r, d))
        G[r].append((l, -d))
    val = [inf] * N
    global_visited = set()

    def bfs(ini):
        flag = True
        q = deque([ini])
        visited = set()
        visited.add(ini)
        while q:
            v = q.popleft()
            for next_v, d in G[v]:
                if next_v in visited:
                    if val[next_v] == val[v] + d:
                        continue
                    else:
                        return False
                val[next_v] = val[v] + d
                visited.add(next_v)
                global_visited.add(next_v)
                q.append(next_v)
        return True

    can = True
    for i in range(N):
        if i in global_visited:
            continue
        v = i
        val[v] = 0
        if not bfs(v):
            can = False
            break

    if can:
        print("Yes")
    else:
        print("No")
    return


main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def dfs(v, p):
        for u, d in tree[v]:
            if u == p:
                continue
            else:
                if dist[u] == f_inf:
                    dist[u] = dist[v] + d
                    dfs(u, v)
                else:
                    if dist[u] != dist[v] + d:
                        print("No")
                        exit()

    dist = [f_inf] * n
    for i in range(n):
        if dist[i] == f_inf:
            dist[i] = 0
            dfs(i, -1)

    print("Yes")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
    visited[s] = True
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if not visited[nv]:
                visited[nv] = True
                dist[nv] = dist[v]+w
                q.append(nv)
            else:
                if dist[nv]!=dist[v]+w:
                    return False
    
    return True

N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

visited = [False]*N
dist = [0]*N
flag = True

for i in range(N):
    if not visited[i]:
        flag &= bfs(i)

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

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"))
      if mode in visited:continue
      visited.add(mode)
      stack.append(mode)
      if ans[mode]==inf:
        ans[mode]=ans[node]+d
      else:
        if ans[node]+d!=ans[mode]:exit(print("No"))
print("Yes")

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    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((r - 1, d))
        E[r-1].append((l - 1, -d))
    Pos = [10 ** 20] * N
    q = deque()
    flag = True
    for i in range(N):
        if Pos[i] == 10 ** 20:
            q.append((i, 0))
            minX, maxX = 0, 0
            while q:
                x, p = q.popleft()
                if Pos[x] == 10 ** 20:
                    minX = min(minX, p)
                    maxX = max(maxX, p)
                    Pos[x] = p
                    for ne, d in E[x]: q.append((ne, p + d))
                elif Pos[x] == p: continue
                else:
                    flag = False
                    break
            else:
                if maxX - minX <= 10 ** 9: continue
                else: flag = False
            if not flag:
                print("No")
                break
    else: print("Yes")
    #print(Pos)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for i in range(m):
        l,r,d=map(int,readline().split())
        G[l].append((r,d))
        G[r].append((l,-d))

    flags=[False]*(n+1)
    flags[0]=True
    inf=10**10
    x=[-inf]*(n+1)
    q=deque([])
    ans=True
    for i in range(1,n+1):
        if ans==False: break
        if flags[i]==False:
            x[i]=0
            flags[i]=True
            q.append(i)
            while len(q)>0:
                now=q.popleft()
                for t in G[now]:
                    nex=t[0]
                    cost=t[1]
                    if x[nex]==-inf:
                        x[nex]=x[now]+cost
                    else:
                        if x[nex]!=x[now]+cost:
                            ans=False
                            break
                    if flags[nex]==False:
                        flags[nex]=True
                        q.append(nex)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
G = [[] for _ in range(n)]
indeg = [0] * 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))

from collections import deque
ng = False
visited = [0] * n
visited_cost = [0] * n

for start in range(n):
    if visited[start]:
        continue
    visited[start] = 1
    st = deque([[start, 0]])
    while st:
        i, cost = st.pop()
        for ni, nd in G[i]:
            if visited[ni] == 0:
                visited[ni] = 1
                visited_cost[ni] = cost + nd
                st.append([ni, cost + nd])
            else:
                # 既に記録されていて、矛盾している場合
                if visited_cost[ni] != cost + nd:
                    # 終了
                    ng = True
                    break
        if ng:
            break
    if ng:
        break
print('No' if ng else 'Yes')

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int, input().split())
A=[[]for _ in range(N)]
V=[False]*N
X=[0]*N
x=0
for i in range(M):
  L,R,D=map(int, input().split())
  A[L-1].append((R-1,D))
  A[R-1].append((L-1,-D))
  
for i in range(N):
  if V[i]==False:
    stack=deque([(i,x)])
    V[i]=True
    while stack:
      now,dx=stack.popleft()
      for new,di in A[now]:
        if V[new]:
          if X[new]!=dx+di:
            print('No')
            exit()
        else:
          X[new]=dx+di
          V[new]=True
          stack.append((new,dx+di))

if max(X)-min(X)>10**9:
  print('No')
else:
  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())
  G[L-1].append((R-1, D))
  G[R-1].append((L-1, -D))
  
visited = [False] * N
xs = [0] * N
xs[0] = 0
x = 0
for i in range(N):
  if visited[i]:
    continue
  stack = deque([(i, x)])
  visited[i] = True
  while stack:
    now, xi = stack.popleft()
    for nx, di in G[now]:
      if visited[nx]:
        if xs[nx] != xi + di:
          print('No')
          exit()
      else:
        xs[nx] = xi + di
        visited[nx] = True
        stack.append((nx, xi+di))
        
if max(xs)-min(xs) > 1000000000:
  print('No')
else:
  print('Yes')

Submission status: Accepted

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

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

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

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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


n, m = map(int, input().split())
UF = WeightedUnionFind(n + 1)

for i in range(m):
    l, r, d = map(int, input().split())
    if UF.same(l, r):
        if d != abs(UF.diff(l, r)):
            exit(print("No"))
    else:
        UF.union(l, r, d)
print("Yes")

Submission status: Accepted

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

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

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

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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


n, m = map(int, input().split())
UF = WeightedUnionFind(n)

for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1;r -= 1
    if UF.same(l, r):
        if d != abs(UF.diff(l, r)):
            exit(print("No"))
    else:
        UF.union(l, r, d)
print("Yes")

Submission status: Accepted

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

people = [-1]*(N)
flag = 0

not_visited = {}
for i in range(N):
    not_visited[i] = True

stack = list(range(N))

while stack:
    now = stack.pop()

    for j in info[now]:
        if not_visited[j[0]]:
            stack.append(j[0])
        
        if people[j[0]] == -1:
            people[j[0]] = people[now] + j[1] 
        else:
            if people[j[0]] != people[now] + j[1]:
                flag = -1

        not_visited[now] = False

if flag != -1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

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

dis = [10**10] * n
edges = [[] for _ in range(n)]

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

for i in range(n):
    if dis[i] == 10**10:
        dis[i] = 0
        q = [i]
        while q:
            l = q.pop()
            for r,d in edges[l]:
                if dis[r] == 10**10:
                    dis[r] = dis[l] + d
                    q.append(r)
                else:
                    if dis[r] - dis[l] != d:
                        print('No')
                        exit()

print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

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

dis = [10**10] * n
edges = [[] for _ in range(n)]

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

for i in range(n):
    if dis[i] == 10**10:
        dis[i] = 0
        q = deque([i])
        while q:
            l = q.popleft()
            for r,d in edges[l]:
                if dis[r] == 10**10:
                    dis[r] = dis[l] + d
                    q.append(r)
                else:
                    if dis[r] - dis[l] != d:
                        print('No')
                        exit()

print('Yes')

Submission status: Accepted

Solution code:
# 深さ優先探索
from sys import stdin

N, M = map(int, stdin.readline().split())

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

t = [None] * (N + 1)
for i in range(1, N + 1):
    if t[i] is not None:
        continue
    t[i] = 0
    s = [i]
    while s:
        j = s.pop()
        for k, l in links[j]:
            if t[k] is None:
                t[k] = t[j] + l
                s.append(k)
            else:
                if t[k] != t[j] + l:
                    print('No')
                    exit()
print('Yes')

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit, stdin


def find(parent, diff_weight, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, diff_weight, t)
    diff_weight[i] += diff_weight[parent[i]]
    parent[i] = t
    return t


def weight(parent, diff_weight, i):
    find(parent, diff_weight, i)
    return diff_weight[i]


def unite(parent, diff_weight, i, j, d):
    d -= weight(parent, diff_weight, j)
    d += weight(parent, diff_weight, i)
    i = find(parent, diff_weight, i)
    j = find(parent, diff_weight, j)
    if i == j:
        return
    diff_weight[j] = d
    parent[i] += parent[j]
    parent[j] = i


setrecursionlimit(10 ** 6)

N, M = map(int, stdin.readline().split())
LRD = [tuple(map(int, stdin.readline().split())) for _ in range(M)]

parent = [-1] * (N + 1)
diff_weight = [0] * (N + 1)
for L, R, D in LRD:
    i = find(parent, diff_weight, L)
    j = find(parent, diff_weight, R)
    if i != j:
        unite(parent, diff_weight, L, R, D)
    else:
        if weight(parent, diff_weight, L) + D != weight(parent, diff_weight, R):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit


def find(parent, diff_weight, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, diff_weight, t)
    diff_weight[i] += diff_weight[parent[i]]
    parent[i] = t
    return t


def weight(parent, diff_weight, i):
    find(parent, diff_weight, i)
    return diff_weight[i]


def unite(parent, diff_weight, i, j, d):
    d -= weight(parent, diff_weight, j)
    d += weight(parent, diff_weight, i)
    i = find(parent, diff_weight, i)
    j = find(parent, diff_weight, j)
    if i == j:
        return
    diff_weight[j] = d
    parent[i] += parent[j]
    parent[j] = i


setrecursionlimit(10 ** 6)

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

parent = [-1] * (N + 1)
diff_weight = [0] * (N + 1)
for L, R, D in LRD:
    i = find(parent, diff_weight, L)
    j = find(parent, diff_weight, R)
    if i != j:
        unite(parent, diff_weight, L, R, D)
    else:
        if weight(parent, diff_weight, L) + D != weight(parent, diff_weight, R):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def pos(x, i):
    j, k = x[i]
    if i == j:
        return i, 0
    l, m = pos(x, j)
    x[i] = (l, m + k)
    return x[i]


setrecursionlimit(10 ** 6)

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

parent = [-1] * (N + 1)
x = [(i, 0) for i in range(N + 1)]
for L, R, D in LRD:
    i = find(parent, L)
    j = find(parent, R)
    if i != j:
        x[j] = (i, D - pos(x, R)[1] + pos(x, L)[1])
        parent[i] += parent[j]
        parent[j] = i
    else:
        if pos(x, L)[1] + D != pos(x, R)[1]:
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

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

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

t = [None] * (N + 1)
for i in range(1, N + 1):
    if t[i] is not None:
        continue
    t[i] = 0
    s = deque([i])
    while s:
        j = s.popleft()
        for k, l in links[j]:
            if t[k] is None:
                t[k] = t[j] + l
                s.append(k)
            else:
                if t[k] != t[j] + l:
                    print('No')
                    exit()
print('Yes')

Submission status: Accepted

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

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

t = [None] * (N + 1)
for i in range(1, N + 1):
    if t[i] is not None:
        continue
    t[i] = 0
    s = [i]
    while s:
        j = s.pop()
        for k, l in links[j]:
            if t[k] is None:
                t[k] = t[j] + l
                s.append(k)
            else:
                if t[k] != t[j] + l:
                    print('No')
                    exit()
print('Yes')

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        P[y]=x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def DD(x):
  dis=0
  while x>=0:
    dis=dis+D[x]
    x=P[x]
  return dis

n,m=map(int,input().split())
uf=UnionFind(n)
D=[0]*n
P=[-1]*n
f=0
for i in range(m):
  l,r,d=map(int,input().split())
  l=l-1
  r=r-1
  if uf.find(l)!=uf.find(r):
    if uf.parents[uf.find(l)]<=uf.parents[uf.find(r)]:
      D[uf.find(r)]=DD(l)+d-DD(r)
    else:
      D[uf.find(l)]=DD(r)-d-DD(l)
    uf.union(l,r)
  else:
    if DD(r)-DD(l)!=d:
      f=1
if f==0:
  print("Yes")
else:
  print("No")

Submission status: Accepted

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

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

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

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


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

for _ in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if uf.same(l, r):
        diff = uf.diff(l, r)
        if diff != d:
            print("No")
            exit()
    else:
        uf.union(l, r, d)

print("Yes")

Submission status: Accepted

Solution code:
import sys
N, M = map(int, sys.stdin.readline().rstrip().split())

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]

unionfind = WeightedUnionFind(N)

for _ in range(M):
    l, r, d = map(int, sys.stdin.readline().rstrip().split())
    if not unionfind.same(l, r):
        unionfind.union(l, r, d)
    else:
        if unionfind.diff(l, r) != d:
            print("No")
            break
else:
    print("Yes")