Problem: 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.

Submission attempts (in order):
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.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(xs))
      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()

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

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

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

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

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:
      r = self.Find_Root(self.root[x])
      self.weight[x] += self.weight[self.root[x]]
      self.root[x] = r
      return r
  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):
    return self.GetWeight(y) - self.GetWeight(x)

n, m = map(int, input().split())
lrd = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n+1)
for l, r, d in lrd:
  if not uf.isSameGroup(l, r):
    uf.Unite(l, r, d)
  else:
    if uf.Diff(l, r) != d:
      print('No')
      exit()

print('Yes')


Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted