Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Accepted

Solution code:
from collections import*
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,m,*t=map(int,open(0).read().split())
u=UnionFind(n+1)
f=defaultdict(list)
e=defaultdict(list)
for l,r,d in zip(t[::3],t[1::3],t[2::3]):
    u.unite(l,r)
    e[l].append((r,d))
for i in range(n+1):
    f[u.root(i)].append(i)
for t in f.values():
    if len(t)<3:continue
    outs=defaultdict(list)
    ins=defaultdict(int)
    for i in t:
        outs[i]=[j for j,v in e[i]]
        for j in outs[i]:
            ins[j]+=1
    q=deque(v1 for v1 in t if ins[v1]==0)
    res=[]
    while q:
        v1=q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2]-=1
            if ins[v2]==0:
                q.append(v2)
    if not res:
        print('No')
        exit()
    c=defaultdict(int)
    for i in res:
        for j,v in e[i]:
            if c[j]and c[j]!=c[i]+v:
                print('No')
                exit()
            c[j]=c[i]+v
print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
N,M = map(int, input().split())
input = sys.stdin.readline
LRD = [ [int(j) for j in input().split()] for _ in range(M)]

data = [x for x in range(N+1)]
rank = [0]  * (N+1)
diff_weight = [0] * (N+1)

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

def weight(x):
    # _ = root(x)
    return diff_weight[x]


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

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

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

for i in range(M):
    L,R,D = LRD[i]
    # print(L,R,D)
    if not issame(L,R):
        _  = merge(L,R,D)
    else:
        if diff(L,R) != D:
            print("No")
            exit(0)
            
print("Yes")

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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())
Un = WeightedUnionFind(N+1)

ans = "Yes"
for _ in range(M):
    l, r, w = map(int, input().split())
    if Un.same(l, r):
        if Un.diff(l, r) != w:
            ans = "No"
            break
    else:
        Un.union(l, r, w)
print(ans)

Submission status: Accepted

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

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

xs = [None for _ in range(n)]

ps = [[] for _ in range(n)]

for lrd in lrds:
    l, r, d = lrd
    ps[l-1].append((r-1, d))
    ps[r-1].append((l-1, -d))

not_decided = set(range(n))

def solve():
    while len(not_decided) != 0:
        t = not_decided.pop()
        xs[t] = 0

        stack = [t]
        while len(stack) != 0:
            c = stack.pop()
            for p in ps[c]:
                another, relative_position = p
                if another in not_decided:
                    xs[another] = xs[c] + relative_position
                    not_decided.remove(another)
                    stack.append(another)
                else:
                    if xs[another] != xs[c] + relative_position:
                        return False
    return True

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
class P_UnionFind:
    def __init__(self, n):
        self.p=[i for i in range(n)]
        self.r=[0 for i in range(n)]
        self.d=[0 for i in range(n)]

    def root(self,x):
        if self.p[x]==x:
            return x
        else:
            tmp = self.root(self.p[x])
            self.d[x] += self.d[self.p[x]]
            self.p[x] = tmp
            return self.p[x]
    
    def weight(self,x):
        self.root(x)
        return self.d[x]

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

    def uni(self,x,y,w):
        if self.same(x,y) and self.diff(x,y)!=w:
            return False
        w+=self.weight(x)
        w-=self.weight(y)
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.r[x]<self.r[y]:
            self.p[x]=y
            self.d[x]=-w
        else:
            self.p[y]=x
            self.d[y]=w
            if self.r[x]==self.r[y]:
                self.r[x]+=1
    
    def same(self,x,y):
        return self.root(x)==self.root(y)


n,m=map(int,input().split())
uf=P_UnionFind(n)
d=[-1 for i in range(n)]
d[0]=0
data=[]
for i in range(m):
    a,b,c=map(int,input().split())
    if uf.uni(a-1,b-1,c) == False:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
inf = 10**10

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


for i in range(n):
    if x[i] == inf:
        x[i]=0
        q = deque([i])
        while len(q)!=0:
            now = q.popleft()
            for e in edge[now]:
                if x[e[0]] == inf:
                    x[e[0]] = x[now]+e[1]
                    q.append(e[0])
                elif x[e[0]]-x[now]!=e[1]:
                    print("No")
                    exit()

print("Yes")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
#lef[i]:iの左親,ran[i]:iの左親までの距離
lef = list(range(n+1))
ran = [0]*(n+1)

#左親の発見および更新
def f(x):
    if lef[x]==x:
        return x
    #ran[x] = ran[x]+ran[lef[x]]
    lef[x],ran[x]= f(lef[x]),ran[x]+ran[lef[x]]
    
    return lef[x]

for i in range(m):
    l,r,d = map(int,input().split())
    a = f(l)
    b = f(r)
    if a == b and ran[r]-ran[l] != d:
        print("No")
        exit()
    else:
        lef[b] = a
        ran[b] = ran[l]+d-ran[r]

print("Yes")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
edge =[[] for _ in range(N+1)]
for _ in range(M):
    l,r,d = map(int,input().split())
    edge[l].append([r,d])
    edge[r].append([l,-d])
G = [None]*(N+1)
ok = True
stack = []
for x in range(1,N+1):
    if G[x] is not None: continue
    G[x] = 0
    stack = [x]
    while stack:
        v = stack.pop()
        for to,d in edge[v]:
            if G[to] is None:
                G[to] = G[v] + d
                stack.append(to)
            else:
                if G[to] != G[v] + d:
                    ok = False
                    break
    if ok == False:
        break
print('Yes' if ok else 'No')

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
LRD = [[int(_) for _ in input().split()] for _ in range(M)]
G = {}
for l, r, d in LRD:
    l -= 1
    r -= 1
    #0-indexed
    G[l] = G.get(l, {})
    G[r] = G.get(r, {})
    G[l][r] = d
    G[r][l] = -d
INF = float('inf')
D = [INF] * N
for i in range(N):
    if i in G and D[i] == INF:
        D[i] = 0
        table = []
        while True:
            for k, v in G[i].items():
                if D[k] == INF:
                    table += [k]
                    D[k] = D[i] + v
                elif D[k] != D[i] + v:
                    print('No')
                    exit()
            if table:
                i = table.pop()
            else:
                break
print('Yes')

Submission status: Accepted

Solution code:
import sys

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

visited = [False] * n

def dfs(start):
	global ed, v, visited
	s = [start]
	v[start] = 0
	while s:
		label = s.pop()
		if visited[label] == False:
			visited[label] = True
			for e in ed[label]:
				if v[e[0]] is None:
					v[e[0]] = v[label] + e[1]
					s.append(e[0])
				else:
					if v[e[0]] != v[label] + e[1]:
						print("No")
						sys.exit()
	return

for i in range(n):
	if v[i] is None:
		dfs(i)

print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
Inf = 10000000000
Edge = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    Edge[l-1].append((r-1, d))
    Edge[r-1].append((l-1, -d))
 
Node = [Inf for i in range(N)]
Possible = True
for i in range(N):
    if not Possible:
        break
    elif Node[i] == Inf:
        Node[i] = 0
        Q = deque([i])
        while Q:
            now = Q.popleft()
            for e in Edge[now]:
                if Node[e[0]] == Inf:
                    Node[e[0]] = Node[now] + e[1]
                    Q.append(e[0])
                elif Node[now] + e[1] != Node[e[0]]:
                    Possible = False
                    break
print("Yes" if Possible else "No")

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x],dist[x] = find(par[x]),dist[x]+dist[par[x]]
        return par[x]
N, M = inpl()
par = list(range(N+1))
dist = [0 for _ in range(N+1)]

for _ in range(M):
    l, r, d = inpl()
    fl = find(l)
    fr = find(r)
    if fl != fr:
        par[fr] = fl
        dist[fr] = d + dist[l] - dist[r]
    elif d + dist[l] - dist[r] != 0:
        print('No')
        break
else:
    print('Yes')

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x],dist[x] = find(par[x]),dist[x]+dist[par[x]]
        return par[x]
N, M = inpl()
par = list(range(N+1))
dist = [0 for _ in range(N+1)]

for _ in range(M):
    l, r, d = inpl()
    fl = find(l)
    fr = find(r)
    if fl == fr and d + dist[l] - dist[r] != 0:
        print('No')
        break
    else: 
        par[fr] = fl
        dist[fr] = d + dist[l] - dist[r]
else:
    print('Yes')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
n,m = map(int, input().split())
edge = {}
for _ in range(m):
    l,r,d = map(int,input().split())
    if l not in edge:
        edge[l] = []
    edge[l].append([r,d])
    if r not in edge:
        edge[r] = []
    edge[r].append([l,-1*d])
# print(edge)
x = [None for _ in range(n+1)]

for i in range(1,n+1):
    if x[i] is None:
        x[i] = 0
        q = deque([i])
        while len(q)>0:
            v = q.popleft()
            if v not in edge:
                break
            for u,d in edge[v]:
                # print(v,u,d,x)
                if x[u] is None:
                    x[u] = x[v]+d
                    q.append(u)
                elif x[u]!=x[v]+d:
                    print("No")
                    exit()
        # print(x)

print("Yes")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [set() for _ in range(N + 1)]
for _ in range(M):
    l, r, d = map(int, input().split())
    edge[l].add((r, d))
    edge[r].add((l, -d))

loc = {}
for i in range(1, N + 1):
    stack = []
    if i not in loc:
        loc[i] = 0
        stack.append(i)
    while stack:
        s = stack.pop()
        for t, d in edge[s]:
            if t not in loc:
                loc[t] = loc[s] + d
                stack.append(t)
            elif loc[t] != loc[s] + d:
                print('No')
                exit()

# 同じ座標に２人いることもある
print('Yes')

Submission status: Accepted

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()
from collections import defaultdict
dd = defaultdict(list)

for _ in range(m):
    l,r,d = ai()
    dd[l].append((r,d))
    dd[r].append((l,-d))

pos = [None] * (n+1)

for i in range(1, n+1):
    if pos[i] is not None:
        continue
    pos[i] = 0
    stack = [i]
    while stack:
        s = stack.pop()
        for p,d in dd[s]:
            if pos[p] is None:
                pos[p] = pos[s] + d
                stack.append(p)
            elif pos[p] != pos[s] + d:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)
INF = 10 ** 18

N, M = map(int, raw_input().split())
E = [[] for i in range(N)]
for i in range(M):
    L, R, D = map(int, raw_input().split())
    E[L - 1].append((R - 1, D))
    E[R - 1].append((L - 1, -D))

X = [INF] * N

def func(pos, x):
    if X[pos] != INF:
        return X[pos] == x
    X[pos] = x
    ret = True
    for to, D in E[pos]:
        ret = ret and func(to, x + D)
    return ret

flag = True
for i in range(N):
    if X[i] == INF:
        flag = flag and func(i, 0)

print "Yes" if flag else "No"

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(range(n+1))
x = [0]*(n+1)
def find(i):
    if p[i] == i:
        return i
    p[i], x[i] = find(p[i]), x[i]+x[p[i]]
    return p[i]
for _ in range(m):
    l, r, d = map(int, input().split())
    pl = find(l)
    pr = find(r)
    if pl == pr and x[r]-x[l] != d:
        print('No')
        break
    else:
        p[pr] = pl 
        x[pr] = x[l] + d - x[r]
else:
    print('Yes')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(range(n+1))
x = [0]*(n+1)
def find(i):
    if p[i] == i:
        return i
    p[i],x[i]=find(p[i]),x[i]+x[p[i]] #root->i dist
    return p[i]

for _ in range(m):
    l,r,d=map(int, input().split())
    pl=find(l)
    pr=find(r)
    #pl!=pr means ununited
    if pl==pr and x[r]-x[l]!=d:
        print('No')
        break
    else:
        p[pr]=pl #unite
        x[pr]=x[l]+d-x[r] #calculate dist
else:
    print('Yes')

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
setrecursionlimit(1000000)


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

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

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


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (i,i)
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()
print("Yes")

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

setrecursionlimit(1000000)
N,M = list(map(int,input().split()))

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

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


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)


for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()

print("Yes")

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
setrecursionlimit(1000000)
INF = 10**10
 
(N, M) = reads()
 
edges = [[] for _ in range(N)]
 
for _ in range(M):
    (L, R, D) = reads()
    (L, R) = (L-1, R-1)
    edges[L].append((R, D))
    edges[R].append((L, -D))
 
visited = [False] * N
place = [None] * N
 
def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (m, M) = (INF, -INF)
    for (j, d) in edges[i]:
        if visited[j] and place[j] != place[i] + d:
            # print("v = ", visited)
            # print("p = ", place)
            print("No")
            exit()
        place[j] = place[i] + d
        (x, y) = walk(j)
        (m, M) = (min(m, x), max(M, y))
    return (m, M)
 
for i in range(N):
    if not visited[i]:
        place[i] = 0
        (m, M) = walk(i)
        if M - m > 10**9:
            # print("(m, M) = ", (m, M))
            print("No")
            exit()
 
print("Yes")

Submission status: Accepted

Solution code:
import heapq

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

INF = 10 ** 9 + 1
G, dist = [[] for i in range(N)], [INF for j in range(N)]
check, p = [0 for k in range(N)], [-1 for l in range(N)]


def dijkstra(s):
    dist[s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if check[v[0]] != 2:
                if dist[u[1]] + v[1] < dist[v[0]]:
                    dist[v[0]], check[v[0]] = dist[u[1]] + v[1], 1
                    heapq.heappush(pq, (dist[v[0]], v[0]))


def main():
    data = []
    for i in range(M):
        l, r, d = map(int, input().split())
        G[l-1].append((r-1, d))
        p[r-1] = l - 1
        data.append((l, r, d))

    for i in range(N):
        if p[i] == -1:
            dijkstra(i)

    for i in range(M):
        l, r, d = data[i]
        if dist[r-1] - dist[l-1] != d:
            print("No")
            break
    else:
        print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
xs = [tuple(map(int, input().split())) for _ in range(m)]

union = {x:(x, 0) for x in range(1, n+1)}
def root(n):
    if union[n][0] == n:
        return union[n]
    n1, d1 = union[n]
    n2, d2 = root(n1)
    union[n] = (n2, d2+d1)
    return union[n]

for l, r, d in xs:
    n1, d1 = root(l)
    n2, d2 = root(r)
    if n1 != n2:
        union[n2] = (n1, d + d1 - d2)
    elif d != d2 - d1:
        print('No')
        break
else:
    print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
 
N,M=map(int,input().split())
Graph=[[] for i in range(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,-D))
visit=[False]*N
dist=[0]*N
 

for i in range(N):
  if not visit[i]:
    visit[i]=True
    A=deque()
    A.append(i)
    while A:
      x=A.pop()
      for y,d in Graph[x]:
        if visit[y] and (dist[y]!=d+dist[x]):
          print('No')
          exit()
        elif not visit[y]:
          visit[y]=True
          A.append(y)
          dist[y]=d+dist[x]
print('Yes')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**8)

def find(x):	#xの根を返す
	global table
	global diff_weight
	
	if table[x] == x:
		return x
	else:
		root = find(table[x])
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		table[x] = root	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x) 
	x = find(x)	
	y = find(y)
	
	if x == y:
		return
	
	if rank[x] < rank[y]:
		x,y = y,x
		w = -w
	
	table[y] = x
	diff_weight[y] = w
	
	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]
		
def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))

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

table = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N)]	#木の長さ
diff_weight = [0 for i in range(N)]


for i in range(M):
	a,b,D = (map(int,input().split()))
	a -= 1
	b -= 1
	if check(a,b):
		if diff(a,b) != D:
			print('No')
			sys.exit()
	else:
		union(a,b,D)
	
	
print ('Yes')

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10 ** 6)

class Impossible(ValueError):
    pass

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

    adj = [[] for i in range(n)]
    parents = [i for i in range(n)]
    for i in range(m):
        l, r, d = lrds[i]
        union(parents, l, r)
        adj[l].append((r, d))
        adj[r].append((l, -d))

    ds = set()
    for i in range(n):
        ds.add(find(parents, i))

    pos = [None for i in range(n)]
    try:
        for i in ds:
            pos[i] = 0
            dfs(adj, pos, i)
        print("Yes")
    except Impossible:
        print("No")

def dfs(adj, pos, x):
    for y, d in adj[x]:
        if pos[y] is None:
            pos[y] = pos[x] + d
            dfs(adj, pos, y)
        elif pos[y] != pos[x] + d:
            raise Impossible

def find(p, x):
    if p[x] != x:
        p[x] = find(p, p[x])
    return p[x]

def union(p, x, y):
    p[find(p, y)] = find(p, x)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n, m = f.read_int_list()
    g = collections.defaultdict(list)
    for _ in xrange(m):
        l, r, d = f.read_int_list()
        g[l].append((r, d))
        g[r].append((l, -d))

    dst = [None]*(n+1)

    for i in xrange(1, n+1):
        if dst[i] is not None: continue
        dst[i] = 0
        que = [i]
        while len(que) > 0:
            v0 = que.pop()
            for vi, di in g[v0]:
                if dst[vi] is not None:
                    if dst[v0]+di != dst[vi]: return 'No'
                else:
                    dst[vi] = dst[v0] + di
                    que.append(vi)

    return 'Yes'


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
class PotUnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
        self.diff_p = [0 for i in range(size)]#親ノードを基準としたポテンシャル

    def root(self, x): #root(x): xの根ノードを返す
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x]) #xをxの根rxに直接つなぎたい
            self.diff_p[x] += self.diff_p[self.parent[x]] #そのために，diff(rx,x)を計算
            self.parent[x] = rx #xをrxに直接つなげる
            return rx

    def merge(self, x, y, dxy): #ポテンシャル差の条件p(y)-p(x)=dxyでxとyのグループをまとめる
        dxy = self.diff_p[x] + dxy - self.diff_p[y] #dxyをdiff(rx,ry)で置き換え
        x = self.root(x) #rxを新たにxと名づける
        y = self.root(y) #ryを新たにyと名づける
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
            dxy = -dxy
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        self.diff_p[y] = dxy #yの相対ポテンシャルを更新
        return True

    def issame(self, x, y): #issame(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): #diff(x,y): xを基準としたyのポテンシャルを返す 
        if self.root(x) == self.root(y): #この時点でxの親はroot(x)
            return self.diff_p[y] - self.diff_p[x]
        else:
            return None

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

uf = PotUnionFind(n)
ans = True
for i in range(m):
    l,r,d=list(map(int,input().split()))
    l-=1;r-=1;
    if uf.issame(l,r):
        ans = d==uf.diff(l,r)
    else:
        uf.merge(l,r,d)
    if ans == False:
        break

if ans == False:
    print('No')
else:
    print('Yes')
#print([uf.root(i) for i in range(n)])
#print([uf.parent[i] for i in range(n)])
#print([uf.size(i) for i in range(n)])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
        self.diff_potential = [0 for i in range(size)]#親ノードを基準としたポテンシャル

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            rx = self.root(self.parent[x]) #xをxの根rxに直接つなぎたい
            self.diff_potential[x] += self.diff_potential[self.parent[x]] #そのために，diff(rx,x)を計算
            self.parent[x] = rx #xをrxに直接つなげる
            return rx

    def merge(self, x, y, diffxy): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        diffxy = self.diff_potential[x] + diffxy - self.diff_potential[y] #diffxyをdiff(rx,ry)で置き換え
        x = self.root(x) #rxを新たにxと名づける
        y = self.root(y) #ryを新たにyと名づける
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
            diffxy = -diffxy
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        self.diff_potential[y] = diffxy #yの相対ポテンシャルを更新
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue，違うならFalse
        return self.root(x) == self.root(y)
        
    def diff(self,x,y): #diff(x,y): xを基準としたyのポテンシャルを返す 
        if self.root(x) == self.root(y): #この時点でxの親はroot(x)
            return self.diff_potential[y] - self.diff_potential[x]
        else:
            return None

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

uf = UnionFind(n)
ans = True
for i in range(m):
    l,r,d=list(map(int,input().split()))
    l-=1;r-=1;
    if uf.issame(l,r):
        ans = d==uf.diff(l,r)
    else:
        uf.merge(l,r,d)
    if ans == False:
        break

if ans == False:
    print('No')
else:
    print('Yes')
#print([uf.root(i) for i in range(n)])
#print([uf.parent[i] for i in range(n)])
#print([uf.size(i) for i in range(n)])