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: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
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 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 pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    r = [0] * n
    f = [False] * n
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))
        f[r-1] = False

    b = ['s'] * n
    def g(i,c):
        if f[i] and c != 's':
            return False
        if b[i] != 's':
            if c == 's':
                return True
            return b[i] == c
        if c == 's':
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,'s'):
            return 'No'
    return 'Yes'


print(main())

Submission status: Memory Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
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 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 pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    e = collections.defaultdict(list)
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if time.time() - start > 1.3:
                return True
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Memory Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
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 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 pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    e = collections.defaultdict(list)
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        if time.time() - start > 0.9:
            return True
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Memory Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
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 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 pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    e = collections.defaultdict(list)
    for _ in range(m):
        l,r,d = LI()
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        if time.time() - start > 0.9:
            return True
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Memory Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**6)

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    start = time.time()
    n,m = LI()
    e = [[] for _ in range(n)]
    for _ in range(m):
        l,r,d = LI()
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if time.time() - start > 0.9:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Memory Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**6)

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if time.time() - start > 0.88:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Memory Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**6)

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if time.time() - start > 0.89:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Memory Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**6)

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if time.time() - start > 0.85:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Accepted

Solution code:
class DSUWeighted():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n
        self.wt = [0] * n

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        order = [x]
        while self.par_size[x] >= 0:
            x = self.par_size[x]
            order.append(x)
        for s in order[:-1][::-1]:
            self.wt[s] += self.wt[self.par_size[s]]
            self.par_size[s] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def merge(self, a, b, w):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        w += self.wt[a] - self.wt[b]
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]:
            x, y = y, x
            w = -w
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        self.wt[y] = w
        return x

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

import sys
input = sys.stdin.buffer.readline

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

uf = DSUWeighted(N)

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

Submission status: Accepted

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

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

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


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

wuf = WeightedUnionFind(N+1)

ans = 'Yes'
for i in range(M):
    L, R, D = map(int, input().split())

    if wuf.is_same(L, R):
        if wuf.diff(L, R) != D:
            ans = 'No'
            break
    else:
        wuf.union(L, R, D)

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0] * n


def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x, y, z):
    s, ws = find(x)
    t, wt = find(y)
    # print(ws, wt)
    if s == t:
        if ws - wt == z:
            pass
        else:
            print('No')
            exit(0)
    else:
        if ws < z + wt:
            par[s] = t
            diff[s] = z + wt - ws
        else:
            par[t] = s
            diff[t] = ws - z - wt


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

print('Yes')

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10001000)

class UnionFindWeighted:
    def __init__(self, n):                      #初期化
        self.n = n                              # 要素数
        self.parents = [i for i in range(n)]    # 親
        self.ranks = [0] * n                    # 木の深さ
        self.sizes = [1] * n                    # グループの要素数
        self.weights = [0] * n                  # 親との重み

    def find(self, x):          #親を出力
        if self.parents[x] == x:
            return x
        else:
            p = self.find(self.parents[x])
            self.weights[x] += self.weights[self.parents[x]]
            self.parents[x] = p
            return p

    def unite(self, x, y, w):          # ユニオン
        # a[x]->a[y]  の差はw  # a[y]=a[x]+w
        rx = self.find(x)
        ry = self.find(y)
        wx = self.weight(x)
        wy = self.weight(y)
        if rx == ry: return
        if self.ranks[rx] > self.ranks[ry]:
            rx , ry = ry, rx    #ryを親にする
            wx , wy = wy, wx
            w *= -1
            print("a")
        self.parents[rx] = ry
        self.sizes[ry] += self.sizes[rx]
        self.weights[rx] = wy - wx - w
        if self.ranks[rx]==self.ranks[ry]:
            self.ranks[rx] += 1

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def size(self, x):          #グループの要素数
        root = self.find(x)
        return self.sizes[root]

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if i == x}

    def group_count(self):      #グループの個数
        return len(self.roots())

    def all_group_members(self):      #グループのメンバー一覧
        return {r: self.members(r) for r in self.roots()}

    def weight(self, x):       #重みの差
        _ = self.find(x)
        return self.weights[x]

    def diff(self, x, y):       #重みの差
        return self.weight(y) - self.weight(x)

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

################

n, m = map(int, input().split())
uf = UnionFindWeighted(n)
for _ in range(m):
    a, b, w = map(int,input().split())
    a -= 1
    b -= 1
    if uf.same(a, b):
        if uf.diff(a, b)!=w:
            print('No')
            exit()
    else:
        uf.unite(a, b, w)
print('Yes')

Submission status: Accepted

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

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

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

		#xの木の高さ < yの木の高さ
		if self.rank[rx] < self.rank[ry]:
			self.par[rx] = ry
			self.weight[rx] = w - self.weight[x] + self.weight[y]

		#xの木の高さ>=yの木の高さ
		else:
			self.par[ry] = rx
			self.weight[ry] = -w - self.weight[y] + self.weight[x]
			#木の高さが同じだった場合の処理
			if self.rank[rx] == self.rank[ry]:
				self.rank[rx] +=1
	#同じ集合に属するか
	def same(self, x, y):
		return self.find(x) == self.find(y)
	#xからyへのコスト
	def diff(self, x, y):
		return self.weight[x] - self.weight[y]

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

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

	if not wuf.same(l, r):
		wuf.union(l, r, d)

	else:
		if wuf.diff(l, r) !=d:
			print("No")
			exit()
print("Yes")

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
        self.diff_weight = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        r = self.find(self.parent[x])
        self.diff_weight[x] += self.diff_weight[self.parent[x]]
        self.parent[x] = r
        return r
    
    def unite(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.parent[y] = x
        self.diff_weight[y] = w

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

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

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

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) and uf.diff(l,r) != d:
        print("No")
        exit()
    uf.unite(l,r,d)
print("Yes")

Submission status: Accepted

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


class Graph:
    class Edge:
        def __init__(self, to, cost):
            """
            :param to:  終点ノード
            :param cost: 辺の重み
            """
            self.to, self.cost = to, cost

    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [[] for _ in range(self.n)]
        self.dist = [None] * self.n
        self.info = [-1]*self.n
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append(self.Edge(y, cost))
        if self.directed == False:
            self.edges[y].append(self.Edge(x, cost))

    def bfs(self, start, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.dist = [None] * self.n
        p, t, dist = start, time, 0
        self.dist[p] = 0
        next_set = deque([(p, t, dist)])

        while next_set:
            p, t, dist = next_set.popleft()
            for edge in self.edges[p]:
                q, cost = edge.to, edge.cost
                if self.dist[q] is not None:
                    if self.dist[q] != dist + cost:
                        print("No")
                        exit()
                    continue
                self.dist[q] = dist + cost
                next_set.append((q, t + 1, dist + cost))
        return True

##################################################################################################

N, M = map(int, input().split())
graph = Graph(N, directed=True, decrement=True, destroy=False)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)
    graph.add_edge(y, x, -cost)
for i in range(1,N+1):
    if graph.dist[i-1] is None:
        graph.bfs(i, goal=-1, time=0, save=True)
print("Yes")

Submission status: Accepted

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

def f(hito, zahyo):
  x[hito]=zahyo
  for tsugi in links[hito]:
    if x[tsugi[0]]==None:
      f(tsugi[0], zahyo+tsugi[1])
    else:
      if x[tsugi[0]]!=zahyo+tsugi[1]:
        print('No')
        exit()

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])
  
x=[None]*(N+1)
for i in range(1, N+1):
  if x[i]==None:
    f(i, 0)
    
print('Yes')

Submission status: Accepted

Solution code:
def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        p = find(par[x])
        diff_w[x] += diff_w[par[x]]
        par[x] = p
        return p


def weight(x):
    '''
    xの根からの距離を求める
    '''
    find(x)
    return diff_w[x]


def union(x, y, w):
    '''
    w[y] = w[x] + w となるようにxとyの属する集合を併合する
    '''
    w += weight(x) - weight(y)
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x
        w = -w
    par[x] += par[y]
    par[y] = x
    diff_w[y] = w
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


def size(x):
    '''
    xが属する集合の個数を求める
    '''
    return -par[find(x)]


def diff(x, y):
    '''
    xとyが同じ集合に属するときの w[y] - w[x] を求める
    '''
    return weight(y) - weight(x)


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

par = [-1] * n
diff_w = [0] * n

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

    if same(l-1, r-1):
        if diff(l-1, r-1) != d:
            print('No')
            exit()
    else:
        union(l-1, r-1, d)

print('Yes')

Submission status: Accepted

Solution code:
def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        p = find(par[x])
        diff_w[x] += diff_w[par[x]]
        par[x] = p
        return p


def weight(x):
    '''
    xの根からの距離を求める
    '''
    find(x)
    return diff_w[x]


def union(x, y, w):
    '''
    w[y] = w[x] + w となるようにxとyの属する集合を併合する
    '''
    w += diff_w[x] - diff_w[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x
        w = -w
    par[x] += par[y]
    par[y] = x
    diff_w[y] = w
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


def size(x):
    '''
    xが属する集合の個数を求める
    '''
    return -par[find(x)]


def diff(x, y):
    '''
    xとyが同じ集合に属するときの w[y] - w[x] を求める
    '''
    return weight(y) - weight(x)


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

par = [-1] * n
diff_w = [0] * n

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

    if same(l-1, r-1):
        if diff(l-1, r-1) != d:
            print('No')
            exit()
    else:
        union(l-1, r-1, d)

print('Yes')

Submission status: Accepted

Solution code:
def find(x, U, r, w): #x: ノード名、U:前のノードの配列 w:前のノードからの距離の配列、r:深さ
  if x == U[x]:
    return (x, w[x])
  else:
    k = find(U[x], U, r, w)
    #付け替え処理
    w[x] += w[U[x]]
    U[x] = k[0]
    #print(k)
    return (U[x],w[x])

def merge(a, b, U, r, w, w_add): #w_add　aにbを付け加える時、距離をwはなす
  a = find(a, U, r, w)[0]
  b = find(b, U, r, w)[0]
  if a == b:#何もしない
    return  
  """
  if r[a] < r[b]:
    a, b = b, a #a（深い）にb（浅い）をくっつける
  U[b] = a  
  if r[a] == r[b]:#もともと同じ深さの時だけ、結合後の深さが１増えるため
    r[a] += 1
  """
  U[b] = a
  r[a] = max(r[a], r[b]+1)
  w[b] += w_add
  return

N, M = map(int,input().split())
U = [i for i in range(N)]#前のノード（自分が先頭の時は自分の値）
w = [0 for _ in range(N)]#前のノードとの距離
r = [0 for _ in range(N)]#自分の木の深さ（自分が先頭の時のみ）

ans = True
for _ in range(M):
  
  L, R, D = map(int,input().split())
  L -= 1
  R -= 1
  t1 = find(L, U, r, w)
  t2 = find(R, U, r, w)
  #print(U,w)
  if t1[0] == t2[0] and not(t2[1] - t1[1] == D):
    ans = False 
    break
  if not(t1[0] == t2[0]):
    D -= t2[1] - t1[1]
    if r[L] < r[R]:
      L, R = R, L
      D = -D
    merge(L, R, U, r, w, D)
  
print("Yes" if ans else "No")

Submission status: Accepted

Solution code:
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    q = deque([])
    visited = set()
    inf = 10 ** 10
    dist = [-inf] * (n + 1)

    for i in range(m):
        a, b, k = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k


    def dfs(u):
        q.append(u)
        while q:
            v = q.pop()
            visited.add(v)
            for x in g[v]:
                if x not in visited:
                    if ref[(v, x)] != []:
                        y = ref.get((v, x))
                        if dist[x] == -inf:
                            dist[x] = dist[v] + y
                        elif dist[x] != dist[v] + y:
                            print("No")
                            exit()
                    else:
                        y = ref.get((x, v))
                        if dist[x] == -inf:
                            dist[x] = dist[v] - y
                        elif dist[v] != dist[x] + y:
                            print("No")
                            exit()
                    q.append(x)


    for i in range(1, n + 1):
        if i not in visited:
            dist[i] = 1
            dfs(i)
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class WeightedUnionFind(object):
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.weight = [0] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.root(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.root(x)
        ry = self.root(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

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


n, m = map(int, input().split())
wuf = WeightedUnionFind(n)
for _ in range(m):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    if wuf.same(l, r) and wuf.diff(l, r) != d:
        print('No')
        exit()
    wuf.unite(l, r, d)

print('Yes')

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import deque
# people on a line
n, m = map(int, input().split())

graph = {i: {} for i in range(1, n + 1)}


for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = -c



distance = ["inf" for i in range(n + 1)]

# グラフにおいて順に点を決めてって、矛盾がないかどうかを調べる
visited = [False for i in range(n + 1)]
visited[0] = True


def find(x):
    d = deque()
    visited[x] = True
    distance[x] = 0
    d.append(x)
    flag = True
    while d and flag:

        x = d.popleft()
        for node in graph[x]:
            if visited[node] == False:
                visited[node] = True
                d.append(node)
                if distance[node] == "inf":
                    distance[node] = distance[x] + graph[x][node]
                else:
                    if  distance[node] != distance[x] + graph[x][node]:
                        flag = False
                        break
            elif visited[node]==True:
                if distance[node]!=distance[x]+graph[x][node]:
                    flag=False
                    break
         
    if flag:
        return False
    else:
        return True

all_flag = True
not_visited = True
while not_visited and all_flag:
    judge = False
    for i in range(1, n + 1):
        if visited[i] == False:
            judge = True
            if find(i):
                all_flag = False
                break
            else:
                pass

    if not judge:
        not_visited = False

if all_flag:
    print("Yes")

else:
    print("No")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.dist = [0]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            p = self.parents[x]
            self.parents[x]=self.find(self.parents[x])
            self.dist[x] += self.dist[p]
            return self.parents[x]
    def unite(self,x,y,d):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            if self.dist[x]-self.dist[y] != d:
                print("No")
                exit()
        else:
            diff = self.dist[y]+d-self.dist[x]
            if diff>=0:
                self.parents[xRoot] = yRoot
                self.dist[xRoot] += diff
                self.find(x)
            else:
                self.parents[yRoot] = xRoot
                self.dist[yRoot] += abs(diff)
                self.find(y)
N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    L,R,D = map(int,input().split())
    tree.unite(L,R,D)
print("Yes")