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

data =[0]
access = [False]*(n+1)
dis = [0]+[" "]*(n)
q = queue.Queue()
for i in range(n):
    data.append([])

for i in range(m):
    l,r,d = map(int,input().split())

    data[l].append((r,d))
    data[r].append((l,-d))

for i in range(1,n+1):
    data[i].sort(reverse=True)

for i in range(1,n+1):
    if data[i]!=[] and not access[i]: 
        q.put(i)
        access[i] = True
        dis[i] = 0
        while not q.empty():
            l = q.get()

            while data[l]:
                r,d = data[l].pop()
                data[r].remove((l,-d))
                if access[r]:
                    if dis[r] ==dis[l]+d:
                        continue
                    else:
                        print("No")
                        exit(0)
                else:
                    access[r] = True
                    dis[r] = dis[l]+d
                    q.put(r)
print("Yes")

Submission status: Accepted

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

#tree = [None] * (N + 1)
tree = [[i, 0] for i in range(N + 1)]

def parent(n):
    p = n
    while tree[p][0] != p:
        p = tree[p][0]
    if p == n:
        return tree[n]
    if p == tree[n][0]:
        return tree[n]
    d = distance_to_root(n)
    tree[n][0] = p
    tree[n][1] = d
    return tree[n]

def distance_to_root(n):
    ret = 0
    nn = n
    while tree[nn][0] != nn:
        ret += tree[nn][1]
        nn = tree[nn][0]
    return ret

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def weight(x):
        root(x)
        return d[x]
    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    d = [0 for i in range(n)]
    for i in range(m):
        x,y,w = LI()
        x -= 1
        y -= 1
        if same(x,y):
            if weight(y)-weight(x) != w:
                print("No")
                quit()
        else:
            unite(x,y,w)
    print("Yes")
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

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

G = [[] for i in range(N + 1)]
for i in range(M):
    l, r, d = map(int, input().split())
    G[l].append([r, d])
    G[r].append([l, - d])
    
def dfs(i):
    for x, d in G[i]:
        if dp[x] == inf:
            dp[x] = dp[i] + d
            if not dfs(x):
                return False
        elif dp[x] != dp[i] + d:
            return False
    return True
    
inf = float('inf')
dp = [inf] * (N + 1)
for i in range(1, N + 1):
    if dp[i] == inf:
        dp[i] = 0
        if not dfs(i):
            print('No')
            break
else:
    print('Yes')

Submission status: Accepted

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

class WeightedUnionfind:

    __slots__ = ['nodes','diff_weight']

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        size_x = -self.nodes[x]; size_y = -self.nodes[y]
        if size_x < size_y:
            x, y = y, x; w = -w
        self.nodes[x] += self.nodes[y]
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

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

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

    def size(self, x):
        return -self.nodes[self.root(x)]

N,M = map(int,input().split())
wuf = WeightedUnionfind(N)
ans = "Yes"
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    if not wuf.same(L,R):
        wuf.unite(L,R,D)
    else:
        if wuf.diff(L,R) != D:
            ans = "No"
            break
print(ans)

Submission status: Accepted

Solution code:
class WeightenedUnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size
        self.__diff_weight = [0] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        r = self.find(self.__root[u])
        self.__diff_weight[u] += self.__diff_weight[self.__root[u]]
        self.__root[u] = r
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int, w: int):
        w += self.weight(u)
        w -= self.weight(v)

        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x
            w = -w

        self.__root[x] += self.__root[y]
        self.__root[y] = x

        self.__diff_weight[y] = w

    def weight(self, u: int)->int:
        self.find(u)
        return self.__diff_weight[u]

    def diff_weight(self, u: int, v: int)->int:
        return self.weight(v) - self.weight(u)


def people_on_a_line(N: int, M: int, queries: list)->bool:
    uf = WeightenedUnionFind(N)
    for l, r, d in queries:
        if uf.same(l-1, r-1):
            if d != uf.diff_weight(l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1, d)

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')

Submission status: Accepted

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

def main():
	N, M = map(int, input().split(" "))
	
	WU = WeightedUnionFind(N)
	ans = "Yes"
	for tmp in range(M):
		L, R, D = map(int, input().split(" "))
		L -= 1
		R -= 1
		if WU.is_same(L, R):
			if WU.diff(L, R) != D:
				ans = "No"
		else:
			WU.union(L, R, D)
	
	print(ans)
		
class WeightedUnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		# 親への重みを管理
		self.weight = [0 for _ in range(n)]
		
	# x が属するグループを探索
	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 self.par[x]
		
	# x と 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
	
	# x と y が同じグループがどうか
	def is_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]
	
if __name__ == "__main__":
	main()

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]

def main():
    max_v, max_e = map(int, input().split())
    uf = WeightedUnionFind(max_v)
    k = []
    s = 0
    for i in range(max_e):
        a,b,w= map(int, input().split())
        a-=1
        b-=1
        if uf.same(a,b):
            if w != uf.diff(a,b):
                print("No")
                break
        else:
            uf.union(a,b,w)
    else:
        print("Yes")
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
N, M = map(int, input().split())
E = [[] for i in range(N + 1)]
for _ in range(M):
    l, r, d = map(int, input().split())
    E[l].append((r, d))
    E[r].append((l, -d))
INF = 10**10
dp = [INF for i in range(N + 1)]


def dfs(i):
    for r, d in E[i]:
        if dp[r] == INF:
            dp[r] = dp[i] + d
            if not dfs(r):
                return False
        elif dp[r] != dp[i] + d:
            return False
    return True


for i in range(1, N + 1):
    if dp[i] == INF:
        dp[i] = 0
        if not dfs(i):
            print('No')
            break
else:
    print('Yes')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def main():
    N, M = map(int, input().split())
    adj = defaultdict(lambda: defaultdict(lambda: 0))
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l][r] = d
        adj[r][l] = -d
    q = deque()
    while len(adj.keys()):
        k = list(adj.keys())[0]
        pos = {k: 0}
        q.append((k, 0))
        while len(q):
            i, x = q.popleft()
            for j in adj[i]:
                if j in pos and pos[j] != x + adj[i][j]:
                    print("No")
                    return
                pos[j] = x + adj[i][j]
                q.append((j, pos[j]))
                del adj[j][i]
            del adj[i]
        if max(pos.values()) - min(pos.values()) > 10**9:
            print("No")
            return
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def main():
    N, M = map(int, input().split())
    adj = defaultdict(lambda: defaultdict(lambda: 0))
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l][r] = d
        adj[r][l] = -d
    q = deque()
    while len(adj.keys()):
        k = list(adj.keys())[0]
        pos = {k: 0}
        q.append((k, 0))
        while len(q):
            i, x = q.popleft()
            for j in adj[i]:
                if j in pos and pos[j] != x + adj[i][j]:
                    print("No")
                    return
                pos[j] = x + adj[i][j]
                q.append((j, pos[j]))
                del adj[j][i]
            del adj[i]
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self, vertexsize):
        self.table = [[-1, 0] for _ in range(vertexsize)]

    def find(self, x):
        dis = 0
        while(self.table[x][0] >= 0):
            dis += self.table[x][1]
            x = self.table[x][0]
        return x, dis

    def union(self, x, y, d):
        xl, xd = self.find(x)
        yl, yd = self.find(y)
        if xl != yl:
            if self.table[xl][0] <= self.table[yl][0]:
                self.table[xl][0] += self.table[yl][0]
                self.table[yl] = [xl, xd + d - yd]
            else:
                self.table[yl][0] += self.table[xl][0]
                self.table[xl] = [yl, -xd - d + yd]
            return True
        else:
            return xd + d == yd

n, m = map(int, input().split())
info = [tuple(map(int, input().split())) for _ in range(m)]
uf = Unionfind(n)
for l, r, d in info:
    ret = uf.union(l-1, r-1, d)
    if not ret:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

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

class WeightedUnionfind:

    __slots__ = ['nodes','diff_weight']

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        rank_x = -self.nodes[x]; rank_y = -self.nodes[y]
        if rank_x < rank_y:
            x, y = y, x; w = -w
        if rank_x == rank_y:
            self.nodes[x] -= 1
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

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

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

    def rank(self, x):
        return -self.nodes[self.root(x)]

N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
wuf = WeightedUnionfind(N+1)
ans = "Yes"
for L,R,D in info:
    if wuf.same(L,R):
        if wuf.diff(L,R) != D:
            ans = "No"
        else:
            pass
    else:
        wuf.unite(L,R,D)
print(ans)

Submission status: Accepted

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

class Unionfind:
    __slots__ = ["nodes","diff_weight"]

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x
    
    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        rank_x = -self.nodes[x]; rank_y = -self.nodes[y]
        if rank_x < rank_y:
            x, y = y, x; w = -w
        if rank_x == rank_y:
            self.nodes[x] -= 1
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]
    
    def diff(self, x, y):
        return self.weight(y) - self.weight(x)
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def rank(self, x):
        return -self.nodes[self.root(x)]
    
N,M = map(int,input().split())
uf = Unionfind(N)
ans = "Yes"
for _ in range(M):
    L, R, D = map(int,input().split())
    L -= 1; R -= 1
    uf.unite(L, R, D)   
    if uf.diff(L, R) != D:
        ans = "No"
        break
print(ans)

Submission status: Accepted

Solution code:
class Unionfind:
    __slots__ = ["nodes","diff_weight"]

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x
    
    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        rank_x = -self.nodes[x]; rank_y = -self.nodes[y]
        if rank_x < rank_y:
            x, y = y, x; w = -w
        if rank_x == rank_y:
            self.nodes[x] -= 1
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]
    
    def diff(self, x, y):
        return self.weight(y) - self.weight(x)
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def rank(self, x):
        return -self.nodes[self.root(x)]
    
N,M = map(int,input().split())
uf = Unionfind(N)
ans = "Yes"
for _ in range(M):
    L, R, D = map(int,input().split())
    L -= 1; R -= 1
    uf.unite(L, R, D)
    if uf.diff(L, R) != D:
        ans = "No"
        break
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

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

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 LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


class WeightedUnionFind:
    __slots__ = ['nodes', 'weight']

    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # ノードの値が負の場合ルートを表し、値は木のランクを表す
        self.weight = [0] * size  # ノードx -> ルート(ノードx)への重みを表す

    # 検索
    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            parent = self.find(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = parent
            return parent

    # 併合
    def unite(self, x: int, y: int, w: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return self.diff_weight(x, y, w)
        else:
            rank_x = -self.nodes[root_x]
            rank_y = -self.nodes[root_y]
            if rank_x < rank_y:
                self.nodes[root_x] = root_y
                self.weight[root_x] = w + self.weight[y] - self.weight[x]
            else:
                self.nodes[root_y] = root_x
                self.weight[root_y] = -w + self.weight[x] - self.weight[y]

                if rank_x == rank_y:
                    self.nodes[root_x] += -1

            return True

    # def is_same(self, x: int, y: int) -> bool:
    #     return self.find(x) == self.find(y)

    def diff_weight(self, x: int, y: int, w: int) -> int:
        return self.weight[x] - self.weight[y] == w


n, m = LI()
uf = WeightedUnionFind(n)
for _ in range(m):
    l, r, d = LI()
    l -= 1
    r -= 1
    if not uf.unite(l, r, d):
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
def prepare(n):
    global nodes,diff_weight
    # ノードは-1で初期化, Nは頂点数
    nodes = [-1]*n
    # 差分重みは0で初期化, Nは頂点数
    diff_weight = [0]*n

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    # xの重みを知りたいので経路圧縮
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# x,yの根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xの木の高さを返す
def rank(x):
    return -nodes[root(x)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 再帰的に根を調べる
        root_x = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        # xを根に直接繋ぎ直す
        nodes[x] = root_x
        return root_x

def unite(x,y,w):
    rx = root(x); ry = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if rx == ry:
        return
    rank_x = rank(rx); rank_y = rank(ry)
    # xの方が木が高いことを想定しているので下の場合はx,yとrx,ryをスワップ,wを-wに
    if rank_x < rank_y:
        x,y = y,x; rx,ry = ry,rx; w = -w
    # 木の高さが同じ場合は繋いだ後の高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[rx] -= 1
    # 低い木の根の差分重みを設定
    diff_weight[ry] = w + weight(x) - weight(y)
    # 低い木の根を高い木の根に繋ぎ直す
    nodes[ry] = rx

N,M = map(int,input().split())
prepare(N)
ans = "Yes"
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
print(ans)

Submission status: Accepted

Solution code:
def prepare(n):
    global nodes,diff_weight
    # ノードは-1で初期化, Nは頂点数
    nodes = [-1]*n
    # 差分重みは0で初期化, Nは頂点数
    diff_weight = [0]*n

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    # xの重みを知りたいので経路圧縮
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# x,yの根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xの木の高さを返す
def rank(x):
    return -nodes[x]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 再帰的に根を調べる
        root_x = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        # xを根に直接繋ぎ直す
        nodes[x] = root_x
        return root_x

def unite(x,y,w):
    # 以下x,yの根について考えるので,重みを補正
    w += weight(x); w -= weight(y)
    x = root(x); y = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if x == y:
        return
    rank_x = rank(x); rank_y = rank(y)
    # xの方が木が高いことを想定しているのでx,yをスワップ,wを-wに
    if rank_x < rank_y:
        x,y = y,x; w = -w
    # 木の高さが同じ場合は繋いだ後の高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[x] -= 1
    # 低い木の根を高い木の根に繋ぎ直す
    nodes[y] = x
    # 低い木の根の差分重みを設定
    diff_weight[y] = w

N,M = map(int,input().split())
prepare(N)
ans = "Yes"
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [-1]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] < 0:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    w += weight(x); w -= weight(y)
    x = root(x); y = root(y)
    if x == y:
        return
    rank_x = -nodes[x]; rank_y = -nodes[y]
    if rank_x >= rank_y:
        nodes[y] = x
        diff_weight[y] = w
        if rank_x == rank_y:
            nodes[x] -= 1
    else:
        nodes[x] = y
        diff_weight[x] = -w

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

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

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
        break
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    w += weight(x); w -= weight(y)
    x = root(x); y = root(y)
    if x == y:
        return
    if rank[x] >= rank[y]:
        nodes[y] = x
        diff_weight[y] = w
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        nodes[x] = y
        diff_weight[x] = -w

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

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

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
        break
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return nodes[x]

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    w += weight(x); w -= weight(y)
    x = root(x); y = root(y)
    if x == y:
        return
    if rank[x] >= rank[y]:
        nodes[y] = x
        diff_weight[y] = w
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        nodes[x] = y
        diff_weight[x] = -w

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

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

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R):
        if diff(L,R) != D:
            ans = "No"
            break
    else:
        unite(L,R,D)

print(ans)

Submission status: Accepted

Solution code:
class vertex : 
    def __init__(self) : 
        self.edges = []

    def add_edge(self, v, weight) : 
        self.edges.append((v, weight))



def dfs(graph, V, memo, d) : 
    for node in [i for (i, b) in enumerate(memo) if not b and i in d] :
        travelled = [0 for _ in xrange(V)]
        if travelled[node] : 
            continue
        
        stack = []
        stack.append((node, 0))
        
        while stack : 
            index, full_weight = stack.pop()
            d[index] = True
            
            for dst, weight in graph[index].edges :
                if travelled[dst] :
                    if travelled[dst] != travelled[index] + weight : 
                        return False
                    continue
                
                travelled[dst] = travelled[index] + weight
                stack.append((dst, travelled[index] + weight))
    
    return True


V, E = map(int, raw_input().strip().split(' '))

graph = [vertex() for _ in xrange(V)]

memo  = [False for _ in xrange(V)]
di    = {}
for _ in xrange(E) : 
    l, r, d = map(int, raw_input().strip().split(' '))
    l -= 1
    r -= 1
    graph[l].add_edge(r, d)
    memo[r] = True
    di[l] = False
    di[r] = False

if dfs(graph, V, memo, di) :
    for k in di : 
        if not di[k] : 
            print "No"
            break
    else : 
        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 unite(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_check(self,x,y):
        return self.find(x)==self.find(y)
    def diff(self,x,y):
        return self.weight[x]-self.weight[y]

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

x = [None for i in range(N)]

def f():
    for i in range(N):
        if x[i] == None:
            x[i] = 0
            q = deque([i])
            while len(q):
                j = q.popleft()
                for k,d in graph[j]:
                    if x[k] == None:
                        q.append(k)
                        x[k] = x[j]+d
                    elif x[k] != x[j]+d:
                        return False
                        
    return True

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