Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

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

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

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

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

D_i are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

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

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

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

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



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


Sample output:
Yes

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
LRD = [[int(i) for i in input().split()] for _ in range(M)]

class WeightedUnionFind() :
    def __init__(self, N) :
        self.parent = [-1] * N
        self.potential = [0] * N
        
    def root(self, x) :
        while self.parent[x] >= 0:
            x = self.parent[x]
        return x

    def unite(self, x, y, w) :
        rx = self.root(x)
        ry = self.root(y)
        
        if rx != ry :
            w = w + self.weight(x) - self.weight(y)
            if self.parent[rx] > self.parent[ry] :
                self.parent[rx] = ry
                self.potential[rx] = -w
            else :
                if self.parent[rx] == self.parent[ry] :
                    self.parent[rx] -= 1
                self.parent[ry] = rx
                self.potential[ry] = w
    
    def same(self, x, y) :
        return self.root(x) == self.root(y)
        
    def size(self, x) :
        return -self.parent[self.root(x)]
    
    def weight(self, x) :
        w = 0
        while self.parent[x] >= 0 :
            w += self.potential[x]
            x = self.parent[x]
        return w
        
    def diff(self, x, y) :
        return self.weight(y) - self.weight(x)
            
def solve() :
    WUF = WeightedUnionFind(N)
    for L, R, D in LRD :
        L, R = L - 1, R - 1
        if WUF.same(L, R) :
            if WUF.diff(L, R) != D :
                return 'No'
        else :
            WUF.unite(L, R, D)
    
    return 'Yes'
    
print(solve())

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
ABC = [list(map(int,input().split())) for i in range(Q)]
edge = [[] for _ in range(N)]

for a,b,c in ABC:
    edge[a-1].append([b-1,c])
    edge[b-1].append([a-1,-c])

numlist = [0] * N
MIN,MAX = 0,0
visited = [False] * N
ans = 0

for i in range(N):
    if visited[i]:
      continue
    stack = [i]
    visited[i] = True
    while stack:
      v = stack.pop()
      for u,d in edge[v]:
        if not visited[u]:
          numlist[u] = numlist[v] + d
          stack.append(u)
          visited[u] = True
ans = 0
for i in range(N):
    if numlist[i] < MIN: MIN = numlist[i]
    elif numlist[i] > MAX: MAX = numlist[i]
    for u,d in edge[i]:
      if numlist[i] + d != numlist[u]:
        ans = -1
        break
    else:
      continue
    break
if ans != -1:
    ans = 'Yes'
else:
  	ans = 'No'

    
print(ans)

Submission status: Accepted

Solution code:

N,Q = map(int,input().split())
ABC = [list(map(int,input().split())) for i in range(Q)]
edge = [[] for _ in range(N)]

for a,b,c in ABC:
    edge[a-1].append([b-1,c])
    edge[b-1].append([a-1,-c])

numlist = [0] * N
MIN,MAX = 0,0
visited = [False] * N
ans = 0

for i in range(N):
    if visited[i]:
      continue
    stack = [i]
    visited[i] = True
    while stack:
      v = stack.pop()
      for u,d in edge[v]:
        if not visited[u]:
          numlist[u] = numlist[v] + d
          stack.append(u)
          visited[u] = True
ans = 0
for i in range(N):
    if numlist[i] < MIN: MIN = numlist[i]
    elif numlist[i] > MAX: MAX = numlist[i]
    for u,d in edge[i]:
      if numlist[i] + d != numlist[u]:
        ans = -1
        break
    else:
      continue
    break
if ans != -1:
    ans = 'Yes'
else:
  	ans = 'No'

    
print(ans)

Submission status: Accepted

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


def main():
    inf = 10 ** 10
    N, M = map(int, input().split())
    x = [inf] * (N + 1)
    adj = defaultdict(lambda: [])
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, start):
        que = deque()
        que.append(start)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()

    for i in range(1, N + 1):
        if seen[i] == 0:
            dfs(adj, i)

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    t1 = time.time()
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, seen, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()
            t2 = time.time()
            if t2 - t1 > 1.8:
                print('Yes')
                sys.exit()
        return seen

    for i in range(1, N + 1):
        if seen[i] == 0:
            seen = dfs(adj, seen, i)

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res


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

ts = topological_sort(edges, n)

if len(ts) != n:
    # Not DAG
    ans = "No"
else:
    # DAG
    dist = [-1] * n
    ans = "Yes"
    for v in ts:
        if dist[v] == -1:
            dist[v] = 0

        for c, u in edges[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + c
            elif dist[u] != dist[v] + c:
                ans = "No"
                break

print(ans)

Submission status: Accepted

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

def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res


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

ts = topological_sort(edges, n)

if len(ts) != n:
    # Not DAG
    ans = "No"
else:
    # DAG
    dist = [-1] * n
    ans = "Yes"
    for i in range(n):
        v = ts[i]
        if dist[v] == -1:
            dist[v] = 0

        for c, u in edges[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + c
            elif dist[u] != dist[v] + c:
                ans = "No"
                break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res




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

ts = topological_sort(edges, n)

if len(ts) != n:
    ans = "No"
    # print("Not DAG")
else:
    # DAG
    dist = [-1] * n
    ans = "Yes"
    for i in range(n):
        v = ts[i]
        if dist[v] == -1:
            dist[v] = 0

        for c, u in edges[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + c
            elif dist[u] != dist[v] + c:
                ans = "No"
                break

print(ans)

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            y = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = y
            return y
    def Weigh(self, x):
        self.Find_Root(x)
        return self.weight[x]
    def Diff(self, x, y):
        return self.Weigh(y) - self.Weigh(x)
    #y - x = w
    def Unite(self, x, y, w):
        w += self.Weigh(x) - self.Weigh(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if x == y:
            if w==0:
                return
            else:
                print('No')
                exit()
        else:
            if self.rnk[x] < self.rnk[y]:
                x, y = y, x
                w = -w
            self.root[x] += self.root[y]
            self.root[y] = x
            self.weight[y] = w
            if self.rnk[x] == self.rnk[y]:
                self.rnk[x] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Size(self, x):
        return -self.root[self.Find_Root(x)]

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
uf=WeightedUnionFind(n)
for x in l:
    uf.Unite(x[0],x[1],x[2])
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")

Submission status: Accepted

Solution code:
def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    INF=float('inf')
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]
    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m
    for x in l:
        x[0]-=1
        x[1]-=1
    #print(l)
    for i in range(m):
        nbr[l[i][0]].append(i)
        nbr[l[i][1]].append(i)
    #print(nbr)
    def sol(i):
        for x in nbr[i]:
            if used[x]:continue
            used[x]=True
            i1=l[x][0]^l[x][1]^i
            dd=d[i]+l[x][2]*(2*(l[x][0]==i)-1)
            if d[i1]!=dd and d[i1]!=INF:
                print('No')
                exit()
            elif d[i1]==INF:
                d[i1]=dd
                sol(i1)
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            sol(i)
    #print(d)
    print('Yes')
solve()

Submission status: Accepted

Solution code:
import collections
def main():
    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for _ in range(M):
        L, R, D = map(int, input().split())
        graph[L][R] = D
        graph[R][L] = -D

    visited = set()
    used = set()
    for i in range(1, N+1):
        if i not in visited:
            dist = dict()
            dist[i] = 0
            cur = [i]
            visited.add(i)
            while cur:
                temp = []
                for j in cur:
                    for k in graph[j]:
                        if (j, k) not in used and (k, j) not in used:
                            used.add((j, k))
                            used.add((k, j))
                            if k not in dist:
                                dist[k] = dist[j] + graph[j][k]
                                temp.append(k)
                                visited.add(k)
                            elif k in dist:
                                if dist[k] != dist[j] + graph[j][k]:
                                    return "No"
                cur = temp

    return "Yes"

if __name__ == '__main__':
    print(main())

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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = IR(3)
    a -= b
    print(a % c)
    return

#B
def B():
    a, b, c, x, ans = II(), II(), II(), II(), 0
    for i in range(a + 1):
        for j in range(b + 1):
            for k in range(c + 1):
                if i * 500 + j * 100 + k * 50 == x:
                    ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(2)]
    for i in range(1, n + 1):
        dp[0][i] += dp[0][i - 1] + a[i - 1]
    a = LI()
    for i in range(1, n + 1):
        dp[1][i] = max(dp[0][i], dp[1][i - 1]) + a[i - 1]
    print(dp[1][-1])
    
    return


class Value_UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.differ_weight[x] += self.differ_weight[self.par[x]]
        self.par[x] = r
        return r

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

    def unit(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y, w = y, x, -w
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        self.differ_weight[y] = w
        return True

    def differ(self, x, y):
        return self.weight(y) - self.weight(x)
#D
def D():
    n, m = LI()
    u = Value_UnionFind(n)
    for _ in range(m):
        l, r, d = LI_()
        if not u.unit(l, r, d + 1):
            if u.differ(l, r) != d + 1:
                print("No")
                return
    print("Yes")


    return

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

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
G = [deque() for i in range(N+1)]
x = [0] * (N+1)
visited = [True] * (N+1)

for i in range(M):
    L, R, D = map(int, input().split())
    G[L].append((R, D))
    G[R].append((L, -D))
    visited[L] = False
    visited[R] = False
    
for i in range(1, N+1):
    if not visited[i]:
        q = G[i]
        visited[i] = True
        
        while q:
            u, d = q.pop()
            
            for v, d_ in G[u]:
                if visited[v]:
                    if x[v] != d+d_:
                        print('No')
                        exit()
                else:
                    visited[v] = True
                    x[v] = d+d_
                    q.append((v, d+d_))
print('Yes')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
 
def Find(x, par, diff_weight):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    px = Find(par[x], par, diff_weight)
    diff_weight[x] += diff_weight[par[x]]
    par[x] = px
    return px
 
def Unite(x, y, par, rank, diff_weight, w):
  w += diff_weight[x] - diff_weight[y]
  x = Find(x, par, diff_weight)
  y = Find(y, par, diff_weight)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      x, y =  y, x
      w = -w
    if rank[x] == rank[y]:
        rank[x] += 1
    par[x] += par[y]
    par[y] = x
    diff_weight[y] = w
 
def Same(x, y, par, diff_weight):
  return Find(x, par,diff_weight) == Find(y, par, diff_weight)
 
def Size(x, par):
  return -par[Find(x)]
 
def Weight(x, par, diff_weight):
  Find(x, par, diff_weight)
  return diff_weight[x]
 
def Diff(x, y, par, diff_weight):
  return Weight(y, par, diff_weight)  - Weight(x, par, diff_weight)
 
par = [-1]*n
rank = [0]*n
diff_weight = [0]*n
for i in range(m):
  l, r, d = map(int, input().split())
  l, r = l-1 ,r-1
  if Same(l, r, par, diff_weight) == False:
    Unite(l, r, par, rank, diff_weight, d)
  else:
    if d != Diff(l, r, par, diff_weight):
      print('No')
      exit()
print('Yes')

Submission status: Accepted

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

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

def Find(x, par, diff_weight):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    px = Find(par[x], par, diff_weight)
    diff_weight[x] += diff_weight[par[x]]
    par[x] = px
    return px

def Unite(x, y, par, rank, diff_weight, w):
  w += diff_weight[x] - diff_weight[y]
  x = Find(x, par, diff_weight)
  y = Find(y, par, diff_weight)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      x, y =  y, x
      w = -w
    if rank[x] == rank[y]:
        rank[x] += 1
    par[x] += par[y]
    par[y] = x
    diff_weight[y] = w

def Same(x, y, par, diff_weight):
  return Find(x, par,diff_weight) == Find(y, par, diff_weight)
 
def Size(x, par):
  return -par[Find(x)]

def Weight(x, par, diff_weight):
  Find(x, par, diff_weight)
  return diff_weight[x]

def Diff(x, y, par, diff_weight):
  return Weight(y, par, diff_weight)  - Weight(x, par, diff_weight)

par = [-1]*n
rank = [0]*n
diff_weight = [0]*n
for i in range(m):
  l, r, d = map(int, input().split())
  l, r = l-1 ,r-1
  if Same(l, r, par, diff_weight) == False:
    Unite(l, r, par, rank, diff_weight, d)
  else:
    if d != Diff(l, r, par, diff_weight):
      print('No')
      exit()
print('Yes')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[[]for i in range(n+1)]
b=[""]*(n+1)
for i in range(m):
    l,r,d=map(int,input().split())
    a[l].append([r,d])
    a[r].append([l,-d])
for i in range(1,n+1):
    if b[i]=="":
        b[i]=0
        k=[i]
        while k:
            s=k.pop()
            for x,y in a[s]:
                if b[x]=="":
                    k.append(x)
                    b[x]=b[s]+y
c="Yes"
for i in range(1,n+1):
    for p,q in a[i]:
        if b[i]+q!=b[p]:
            c="No"
print(c)

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
http://at274.hatenablog.com/entry/2018/02/03/140504


5 5
1 2 2
2 3 3
4 5 4
2 5 10
3 4 3
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    ### 重みが正負逆になる。なんでだ
    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(N):
    uf.find(i)

for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        if d == uf.weight[r] - uf.weight[l]:
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
http://at274.hatenablog.com/entry/2018/02/03/140504


5 5
1 2 2
2 3 3
4 5 4
2 5 10
3 4 3
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    # def calc_weight(self, x):
    #     self.find(x) #圧縮
    #     return self.weight[x]

    # def calc_diff(self, x, y):
    #     return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] = - w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(N):
    uf.find(i)

for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        if d == -uf.weight[r]+uf.weight[l]:
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
LRD = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for L,R,D in LRD:
    E[L-1][R-1] = D
    E[R-1][L-1] = -D

V = [None]*N
breakFlg = False
for i in range(N):
    if V[i]!=None:
      	continue
    V[i] = 0
    q = [i]
    while q:
        j = q.pop()
        v = V[j]
        for k,d in E[j].items():
            if V[k] == None:
                V[k] = v+d
                q.append(k)
ans = True
for l,e in enumerate(E):
    for r,d in e.items():
        ans = ans and V[r]-V[l]==d
    if not ans:
      	break
print("Yes" if ans else "No")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

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

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

# print(nl)
    
seen = [None for _ in range(N + 1)]

def dfs(v, d):
    # print("dfs ", v, d)
    seen[v] = d
    for next_v, D in nl[v]:
        next_d = d + D
        if seen[next_v] is None:
            dfs(next_v, next_d)
        else:
            if seen[next_v] != next_d:
                print('No')
                exit(0)
                
for v in range(1, N + 1):  # すべての連結成分に対してDFS
    if seen[v] is None:
        dfs(v, 0)

print('Yes')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC87 D
#重み付きUnion-Find

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if x == par[x]:
        return par[x]
    y = root(par[x])
    wei[x] += wei[par[x]]
    par[x] = y
    return y

def union(x,y,w):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        par[rx] = ry
        wei[rx] = w - wei[x] + wei[y]
    else:
        par[ry] = rx
        wei[ry] = -w - wei[y] + wei[x]
        if rank[rx] == rank[ry]:
            rank[rx] += 1


n,m = LI()
par = [i for i in range(n)]
rank = [0]*n
wei = [0]*n
for i in range(m):
    l,r,w = LI()
    if root(l-1) != root(r-1):
        union(l-1,r-1,w)
    else:
        if wei[l-1] - wei[r-1] != w:
            print('No')
            quit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

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

seen = [None for _ in range(N + 1)]


def dfs(v, d):
    seen[v] = d
    for next_v, D in nl[v]:
        next_d = d + D
        if seen[next_v] is None:
            dfs(next_v, next_d)
        else:
            if seen[next_v] != next_d:
                print('No')
                exit(0)


for v in range(1, N + 1):  # すべての連結成分に対してDFS
    if seen[v] is None:
        dfs(v, 0)

print('Yes')