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 resolve():

    N,M = map(int,input().split())
    root = list(range(N))
    depth = [1 for _ in range(N)]
    dist = [0 for _ in range(N)]

    def find(a,root,dist):
        if root[a] == a:
            return (a,0)
        else:
            root[a],d = find(root[a],root,dist)
            dist[a] += d
            return(root[a],dist[a])

    def unite(a,b,d,root,depth,dist):
        A,dist_a = find(a,root,dist)
        B,dist_b = find(b,root,dist)

        if A == B:
            if dist_b - dist_a == d:
                return True
            else:
                return False
        else:
            if depth[A] > depth[B]:
                root[B] = A
                depth[A] += depth[B]
                dist[B] = dist_a - dist_b + d
            else:
                root[A] = B
                depth[B] += depth[A]
                dist[A] = dist_a - dist_b - d
            return True
        
    ans = True
    for _ in range(M):
        L,R,D = map(int,input().split())
        if not (unite(L-1,R-1,D,root,depth,dist)):
            ans = False
            break
    print("Yes" if ans else "No")
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def GetWeight(self, x):
      self.Find_Root(x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return self.GetWeight(y)- self.GetWeight(x)
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)

  for i in range(M):
    l, r, d = lrd[i]
    if not U.isSameGroup(l, r):
      U.Unite(l, r, d)
    else:
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def GetWeight(self, x):
      self.Find_Root(x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return self.GetWeight(y)- self.GetWeight(x)
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)

  for i in range(M):
    l, r, d = lrd[i]
    if not U.isSameGroup(l, r):
      U.Unite(l, r, d)
    else:
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def GetWeight(self, x):
      self.Find_Root(x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return abs(self.GetWeight(y)- self.GetWeight(x))
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)

  for i in range(M):
    l, r, d = lrd[i]
    U.Unite(l, r, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.isSameGroup(l, r):
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def GetWeight(self, x):
      self.Find_Root(self, x)
      return self.weight[x]

    def Unite(self, x, y, w):
        w += self.weight[x]
        w -= self.weight[y]
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False

        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        
        self.root[y] = x
        self.weight[y] = w

        return True
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return abs(self.weight[y] - self.weight[x])
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True

  for i in range(M):
    l, r, d = lrd[i]
    U.Unite(l, r, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.isSameGroup(l, r):
      if U.Diff(l, r) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
        if(rx == ry):
            return 
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return abs(self.weight[y] - self.weight[x])
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True

  for i in range(M):
    l, r, d = lrd[i]
    U.Unite(l-1, r-1, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.isSameGroup(l-1, r-1):
      if U.Diff(l-1, r-1) != d:
        print('No')
        exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)

        if(rx == ry):
            return 
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return abs(self.weight[y] - self.weight[x])
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True

  for i in range(M):
    l, r, d = lrd[i]
    U.Unite(l-1, r-1, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.Diff(l-1, r-1) != d:
      print('No')
      exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
 
        if(rx == ry):
            return self.Diff(x, y) == w
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      if self.isSameGroup(x, y):
        return self.weight[y] - self.weight[x]
      else:
        return None

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True

  for i in range(M):
    l, r, d = lrd[i]
    flag = U.Unite(l-1, r-1, d)
    if not flag:
      print('No')
      exit()
  print('Yes')

  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
 
        if(rx == ry):
            return self.Diff(x, y) == w
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      return self.weight[y] - self.weight[x]

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True
  for i in range(M):
    l, r, d = lrd[i]
    flag = U.Unite(l, r, d)
    if not flag:
      print('No')
      exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
        print(rx, ry)
 
        if(rx == ry):
            return self.Diff(x, y) == w
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      return self.weight[y] - self.weight[x]

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True
  for i in range(M):
    l, r, d = lrd[i]
    flag = U.Unite(l, r, d)
    if not flag:
      print('No')
      exit()
  print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
 
        if(rx == ry):
            return self.weight[y] - self.weight[x] == w
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      return self.weight[y] - self.weight[x]

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True
  for i in range(M):
    l, r, d = lrd[i]
    flag = U.Unite(l, r, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.Diff(l, r) != d:
      flag = False
  if not flag:
    print('No')
  else:
    print('Yes')
  
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
 
        if(rx == ry):
            return self.weight[y] - self.weight[x] == w
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      return self.weight[y] - self.weight[x]

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  flag = True
  for i in range(M):
    l, r, d = lrd[i]
    flag = U.Unite(l, r, d)
  if not flag:
    print('No')
  else:
    print('Yes')
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
 
        if(rx == ry):
            return 
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      return self.weight[y] - self.weight[x]

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  for i in range(M):
    l, r, d = lrd[i]
    U.Unite(l, r, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.Diff(l, r) != d:
      print('No')
      exit()
  print('Yes')
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = 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:
            self.root[x] = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            return self.root[x]

    def Unite(self, x, y, w):
        rx = self.Find_Root(x)
        ry = self.Find_Root(y)
        print(rx, ry)
 
        if(rx == ry):
            return 
        elif(self.rnk[rx] > self.rnk[ry]):
            self.root[ry] = rx
            self.weight[ry] = w - self.weight[y] + self.weight[x]
        else:
            self.root[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[y]
            if(self.rnk[rx] == self.rnk[ry]):
                self.rnk[ry] += 1
 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
    def Diff(self, x, y):
      return self.weight[y] - self.weight[x]

def main():
  N, M = map(int, input().split())
  lrd = [list(map(int, input().split())) for _ in range(M)]
  U = UnionFind(N)
  for i in range(M):
    l, r, d = lrd[i]
    U.Unite(l, r, d)
  for i in range(M):
    l, r, d = lrd[i]
    if U.Diff(l, r) != d:
      print('No')
      exit()
  print('Yes')
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

def root(x):
    if par[x]==x:
        return x
    else:
        r =root(par[x])
        ws[x] +=ws[par[x]]
        par[x]=r
        return par[x]

def weight(x):
    root(x)
    return ws[x]
def diff(x,y):
    return weight(x) -weight(y)

def merge(x,y,w):
    if root(x)==root(y):
        if diff(x,y)!=w:
            print('No')
            exit()
        else:
            return
    else:
        if w+weight(y)>=weight(x):
            par[root(x)]=root(y)
            par[x]=y
            ws[x]=w
        else:
            par[root(y)]=root(x)
            par[x]=y
            ws[x]=w

for _ in range(m):
    x,y,z= map(int,input().split())
    x -=1
    y -=1
    merge(x,y,z)

print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def calc(A, B, C, now_t):
    ans = A * now_t + B * math.sin(C * now_t * math.pi)
    return ans


def main():
    num, hint_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(hint_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)
    dist_ind = defaultdict(int)
    for i in range(hint_num):
        l, r , d = data[i]
        graph_data[l].add(r)
        graph_data[r].add(l)
        dist_data[(l, r)] = d
        dist_data[(r, l)] = -1 * d
        dist_ind[(l, r)] = i
        dist_ind[(r, l)] = i

    position = [-1 for i in range(num + 1)]
    dist_visit = [0 for i in range(hint_num)]
    check_point = [0 for i in range(num + 1)]

    flg = 1
    for i in range(hint_num):
        if dist_visit[i]:
            continue
        # dist_visit[i] = 1

        l, r, d = data[i]
        now_set = set()
        next_set = set()
        now_set.add(l)
        now_set.add(r)

        while len(now_set) > 0:
            for now_ele in now_set:
                if position[now_ele] == -1:
                    position[now_ele] = 0

                for next_ele in graph_data[now_ele]:
                    if check_point[next_ele]:
                        continue
                    length = dist_data[(now_ele, next_ele)]
                    len_ind = dist_ind[(now_ele, next_ele)]
                    if dist_visit[len_ind]:
                        continue
                    dist_visit[len_ind] = 1
                    if position[next_ele] == -1:
                        position[next_ele] = position[now_ele] + length
                        next_set.add(next_ele)
                    else:
                        if position[next_ele] != position[now_ele] + length:
                            flg = 0
                            break
                check_point[now_ele] = 1
            now_set = next_set
            next_set = set()

    # print(position)

    max_data = -10 ** 10
    min_data = 10 ** 10
    for i in range(1, num + 1):
        if position[i] == -1:
            continue
        max_data = max(max_data, position[i])
        min_data = min(min_data, position[i])

    if max_data - min_data > 10 ** 9:
        flg = 0

    if flg:
        print('Yes')
    else:
        print('No')





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def calc(A, B, C, now_t):
    ans = A * now_t + B * math.sin(C * now_t * math.pi)
    return ans


def main():
    num, hint_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(hint_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)
    dist_ind = defaultdict(int)
    for i in range(hint_num):
        l, r , d = data[i]
        graph_data[l].add(r)
        graph_data[r].add(l)
        dist_data[(l, r)] = d
        dist_data[(r, l)] = -1 * d
        dist_ind[(l, r)] = i
        dist_ind[(r, l)] = i

    position = [-1 for i in range(num + 1)]
    dist_visit = [0 for i in range(hint_num)]

    flg = 1
    for i in range(hint_num):
        if dist_visit[i]:
            continue
        # dist_visit[i] = 1

        l, r, d = data[i]
        now_set = set()
        next_set = set()
        now_set.add(l)
        now_set.add(r)

        while len(now_set) > 0:
            for now_ele in now_set:
                if position[now_ele] == -1:
                    position[now_ele] = 0

                for next_ele in graph_data[now_ele]:
                    length = dist_data[(now_ele, next_ele)]
                    len_ind = dist_ind[(now_ele, next_ele)]
                    if dist_visit[len_ind]:
                        continue
                    dist_visit[len_ind] = 1
                    if position[next_ele] == -1:
                        position[next_ele] = position[now_ele] + length
                        next_set.add(next_ele)
                    else:
                        if position[next_ele] != position[now_ele] + length:
                            flg = 0
                            break
            now_set = next_set
            next_set = set()

    # print(position)

    max_data = -10 ** 10
    min_data = 10 ** 10
    for i in range(1, num + 1):
        if position[i] == -1:
            continue
        max_data = max(max_data, position[i])
        min_data = min(min_data, position[i])

    if max_data - min_data > 10 ** 9:
        flg = 0

    if flg:
        print('Yes')
    else:
        print('No')





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def calc(A, B, C, now_t):
    ans = A * now_t + B * math.sin(C * now_t * math.pi)
    return ans


def main():
    num, hint_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(hint_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)
    dist_ind = defaultdict(int)
    for i in range(hint_num):
        l, r , d = data[i]
        graph_data[l].add(r)
        graph_data[r].add(l)
        dist_data[(l, r)] = d
        dist_data[(r, l)] = -1 * d
        dist_ind[(l, r)] = i
        dist_ind[(r, l)] = i

    position = [-1 for i in range(num + 1)]
    dist_visit = [0 for i in range(hint_num)]

    flg = 1
    for i in range(hint_num):
        if dist_visit[i]:
            continue
        # dist_visit[i] = 1

        l, r, d = data[i]
        now_set = set()
        next_set = set()
        now_set.add(l)
        now_set.add(r)

        while len(now_set) > 0:
            for now_ele in now_set:
                if position[now_ele] == -1:
                    position[now_ele] = 0

                for next_ele in graph_data[now_ele]:
                    length = dist_data[(now_ele, next_ele)]
                    len_ind = dist_ind[(now_ele, next_ele)]
                    if dist_visit[len_ind]:
                        continue
                    dist_visit[len_ind] = 1
                    if position[next_ele] == -1:
                        position[next_ele] = position[now_ele] + length
                        next_set.add(next_ele)
                    else:
                        if position[next_ele] != position[now_ele] + length:
                            flg = 0
                            break
            now_set = next_set
            next_set = set()

    # print(position)

    if flg:
        print('Yes')
    else:
        print('No')





if __name__ == '__main__':
    main()