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: Wrong Answer

Solution code:
def sol():
    n,m=map(int,input().split())
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    for i in s:
        k={j for j in w[i]}
        g=set()
        cnt=0
        while len(k):
            x=k.pop()
            cnt+=1
            if cnt==8000:
                print("No")
                exit()
                
            if x[0] not in w:
                g.add(x)
            else:
                for j in w[x[0]]:
                    k.add((j[0],j[1]+x[1]))
        y=set()
        for j in g:
            if j[0] in y or j[0]==i:
                print("No")
                exit()
            else:
                y.add(j[0]) 
    print("Yes" if len(s) or m==0 else "No")

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def sol():
    n,m=map(int,input().split())
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    for i in s:
        k={j for j in w[i]}
        g=set()
        cnt=0
        while len(k):
            x=k.pop()
            cnt+=1
            if cnt==5000:
                print("No")
                exit()
                
            if x[0] not in w:
                g.add(x)
            else:
                for j in w[x[0]]:
                    k.add((j[0],j[1]+x[1]))
        y=set()
        for j in g:
            if j[0] in y or j[0]==i:
                print("No")
                exit()
            else:
                y.add(j[0]) 
    print("Yes" if len(s) or m==0 else "No")

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:

n,m=map(int,input().split())
w={}
p,q=set(),set()
for i in range(m):
    l,r,d=[int(i) for i in input().split()]
    if l in w:
        w[l].add((r,d))
    else:
        w[l]={(r,d)}
    p.add(l)
    q.add(r)

s=p-q
for i in s:
    k={j for j in w[i]}
    g=set()
    while len(k):
        x=k.pop()
        if x[0] not in w:
            g.add(x)
        else:
            for j in w[x[0]]:
                k.add((j[0],j[1]+x[1]))
    y=set()
    for j in g:
        if j[0] in y or j[0]==i:
            print("No")
            exit()
        else:
            y.add(j[0])
print("Yes" if len(s) else "No")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
w={}
#t={}
p,q=set(),set()
for i in range(m):
    l,r,d=[int(i) for i in input().split()]
    if l in w:
        w[l].add((r,d))
    else:
        w[l]={(r,d)}
    #t[(l,r)]=d
    p.add(l)
    q.add(r)

#print(w)
#print(t)
s=p-q
#print(s)
for i in s:
    k={j for j in w[i]}
    g=set()
    while len(k):
        x=k.pop()
        if x[0] not in w:
            g.add(x)
        else:
            for j in w[x[0]]:
                k.add((j[0],j[1]+x[1]))
    y=set()
    for j in g:
        if j[0] in y or j[0]==i:
            print("No")
            exit()
        else:
            y.add(j[0])
print("Yes")

Submission status: Wrong Answer

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.weight = [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)
        w = w + self.weight[x] - self.weight[y]
        
        if rx != ry :
            if self.parent[rx] > self.parent[ry] :
                self.parent[rx] = ry
                self.weight[rx] = -w
            else :
                if self.parent[rx] == self.parent[ry] :
                    self.parent[rx] -= 1
                self.parent[ry] = rx
                self.weight[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 diff(self, x, y) :
        wx, wy = 0, 0
        while self.parent[x] >= 0 :
            wx += self.weight[x]
            x = self.parent[x]
        while self.parent[y] >= 0 :
            wy += self.weight[y]
            y = self.parent[y]
        return wy - wx
            
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: Wrong Answer

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

Submission status: Wrong Answer

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.weight = [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)
        w = w - self.weight[x] + self.weight[y]
        
        if rx != ry :
            if self.parent[rx] > self.parent[ry] :
                self.parent[rx] = ry
                self.weight[rx] = w
            else :
                if self.parent[rx] == self.parent[ry] :
                    self.parent[rx] -= 1
                self.parent[ry] = rx
                self.weight[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 diff(self, x, y) :
        wx, wy = 0, 0
        while self.parent[x] >= 0 :
            wx += self.weight[x]
            x = self.parent[x]
        while self.parent[y] >= 0 :
            wy += self.weight[y]
            y = self.parent[y]
        return wx - wy
            
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: Wrong Answer

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

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:
                        return 0, seen
    return 1, seen


for i in range(1, N + 1):
    if seen[i] == 0:
        ok, seen = dfs(adj, seen, i)
        if not ok:
            print('Noq')
            sys.exit()

print('Yesq')

Submission status: Wrong Answer

Solution code:

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

LRD.sort(key = lambda x:x[0])
edge = [[] for _ in range(N+1)]
for l,r,d in LRD:
    edge[l].append([r,d])
    
def find_edge(x,y):
    node = edge[x]
    left = 0
    right = len(node)-1
    while right >= left:
        c = (left + right)//2
        if node[c][0] == y:
            return c
        elif node[c][0] > y:
            right = c-1
        elif node[c][0] < y:
            left = c+1
    return -1
    
import sys


for l,r,d1 in LRD:
    for y,d2 in edge[r]:
        c = find_edge(l,y)
        flag = find_edge(y,l)
        if flag != -1:
            print('No')
            sys.exit()
        if c != -1:
            D = edge[l][c][1]
            if d1 + d2 != D:
                print('No')
                sys.exit()
                
print('Yes')

Submission status: Wrong Answer

Solution code:

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

LRD.sort(key = lambda x:x[0])
edge = [[] for _ in range(N+1)]
for l,r,d in LRD:
    edge[l].append([r,d])
    
def find_edge(x,y):
    node = edge[x]
    left = 0
    right = len(node)-1
    while right >= left:
        c = (left + right)//2
        if node[c][0] == y:
            return c
        elif node[c][0] > y:
            right = c-1
        elif node[c][0] < y:
            left = c+1
    return -1
    
import sys

for i in range(M):
    l,r,d1 = LRD[i]
    
    for y,d2 in edge[r]:
        c = find_edge(l,y)
        if c != -1:
            D = edge[l][c][1]
            if d1 + d2 != D:
                print('No')
                sys.exit()
                
print('Yes')

Submission status: Wrong Answer

Solution code:

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

LRD.sort(key = lambda x:x[0])
edge = [[] for _ in range(N+1)]
for l,r,d in LRD:
    edge[l].append([r,d])
    
def find_edge(x,y):
    node = edge[x]
    left = 0
    right = len(node)-1
    while right >= left:
        c = (left + right)//2
        if node[c][0] == y:
            return c
        elif node[c][0] > y:
            right = c-1
        elif node[c][0] < y:
            left = c+1
    return -1
    
import sys

for i in range(M):
    l,r,d1 = LRD[i]
    
    for y,d2 in edge[r]:
        c = find_edge(l,y)
        if c != -1:
            D = edge[l][c][1]
            if d1 + d2 != D:
                print('No')
                sys.exit()
                
print('Yes')

Submission status: Wrong Answer

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:
                print('No')
                exit()
            else:
                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: Wrong Answer

Solution code:
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
c=0
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):
    if d[i]==INF:
        d[i]=0
    for x in nbr[i]:
        if used[x]:continue
        used[x]=True
        if l[x][0]==i:
            if d[l[x][1]]==INF:
                d[l[x][1]]=d[i]+l[x][2]
            elif d[l[x][1]]!=d[i]+l[x][2]:
                print('No')
                exit()
        else:
            if d[l[x][0]]==INF:
                d[l[x][0]]=d[i]-l[x][2]
            elif d[l[x][0]]!=d[i]-l[x][2]:
                print('No')
                exit()
for i in range(n):
    sol(i)
#print(d)
print('Yes')

Submission status: Wrong Answer

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 (j, k) 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: Wrong Answer

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]
            while cur:
                temp = []
                for j in cur:
                    for k in graph[j]:
                        if (j, k) not in used and (j, k) 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: Wrong Answer

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:
            cur = dict()
            cur[i] = 0
            while True:
                temp = dict()
                for j in cur:
                    for k in graph[j]:
                        if (j, k) not in used and (k, j) not in used:
                            l = cur[j] + graph[j][k]
                            if k not in cur:
                                temp[k] = l
                            elif k in cur and cur[k] != l:
                                return "No"
                            elif k in temp and temp[k] != l:
                                return "No"
                            used.add((j,k))
                            used.add((k,j))
                for k in temp:
                    cur[k] = temp[k]
                if len(temp) == 0:
                    break
        for k in cur:
            visited.add(k)
    return "Yes"

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

Submission status: Wrong Answer

Solution code:
#D問題
N,M = map(int,input().split())
LRD = [list(map(int,input().split())) for i in range(M)]
LRD.sort()

inf = float("inf")
X = [-inf for i in range(N)]
flag = 0
for i in range(M):
    l,r,d = LRD[i][0]-1,LRD[i][1]-1,LRD[i][2]
    if X[l] == -inf and X[r] == -inf:
        X[l] = 0
        X[r] = d
    elif X[l] == -inf:
        X[l] = X[r]-d
    elif X[r] == -inf:
        X[r] = X[l]+d
    else:
        if X[l]+d == X[r]:
            pass
        else:
            flag = 1
            break
        

if flag == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#D問題
N,M = map(int,input().split())
LRD = [list(map(int,input().split())) for i in range(M)]

inf = float("inf")
X = [-inf for i in range(N)]
flag = 0
for i in range(M):
    l,r,d = LRD[i][0]-1,LRD[i][1]-1,LRD[i][2]
    if X[l] == -inf and X[r] == -inf:
        X[l] = 0
        X[r] = d
    elif X[l] == -inf:
        X[l] = X[r]-d
    elif X[r] == -inf:
        X[r] = X[l]+d
    else:
        if X[l]+d == X[r]:
            pass
        else:
            flag = 1
            break
        

if flag == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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:
    # 経路圧縮
    diff_weight[x] += diff_weight[par[x]]
    par[x] = Find(par[x], par, diff_weight)
    return par[x]

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: Wrong Answer

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:
    # 経路圧縮
    par[x] = Find(par[x], par, diff_weight)
    diff_weight[x] += diff_weight[par[x]]
    return par[x]

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):
  return diff_weight[Find(x, par, diff_weight)]

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: Wrong Answer

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:
    # 経路圧縮
    par[x] = Find(par[x], par, diff_weight)
    diff_weight[x] += diff_weight[par[x]]
    return par[x]

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: Wrong Answer

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:
    # 経路圧縮
    par[x] = Find(par[x], par, diff_weight)
    diff_weight[x] += diff_weight[par[x]]
    return par[x]

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, diff_weight):
  return diff_weight[x]

def Diff(x, y, diff_weight):
  return Weight(y, diff_weight)  - Weight(x, 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 != abs(Diff(l, r, diff_weight)):
      print('No')
      exit()
else:
  print('Yes')

Submission status: Wrong Answer

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:
    # 経路圧縮
    par[x] = Find(par[x], par, diff_weight)
    diff_weight[x] += diff_weight[par[x]]
    return par[x]

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, diff_weight):
  return diff_weight[x]

def Diff(x, y, diff_weight):
  return Weight(y, diff_weight)  - Weight(x, 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, diff_weight):
      print('No')
      exit()
else:
  print('Yes')

Submission status: Wrong Answer

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: Wrong Answer

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(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        print(d,uf.calc_diff(r,l))
        if d == uf.calc_diff(r,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]))