Problem p03450 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

class WeightedUnionFindTree:
  def __init__(self, n):
    self.par = list(range(n))
    self.rank = [0 for _ in range(n)]
    self.weight = [0 for _ in range(n)]
   
  def root(self, t):
    if t == self.par[t]:
      return t
    # 経路圧縮してみる
    r = self.root(self.par[t])
    self.weight[t] += self.weight[self.par[t]]
    self.par[t] = r
    return r
   
  def rec_weight(self, t):
    if t == self.par[t]:
      return 0
    return self.weight[t] + self.rec_weight(self.par[t])
   
  def same(self, x, y):
    return self.root(x) == self.root(y)
     
  def unite(self, x, y, w):
    rootx = self.root(x)
    rooty = self.root(y)
    if rootx != rooty:
      if y != rooty:
        # 直接yにつなげる
        self.weight[rootx] = w - self.rec_weight(x)
      else:
        # 根につなげる
        self.weight[rootx] = w - (self.weight[x] - self.weight[y])
      # ここで親を更新
      self.par[rootx] = y
    else:
      return w == self.diff(x, y)
 
  def diff(self, x, y):
    return self.rec_weight(x) - self.rec_weight(y)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]


wuft = WeightedUnionFindTree(n+1)
flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  a = wuft.unite(l, r, d)
  if a is not None:
    if a == False:
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(wuft.par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(wuft.weight)]
print()
"""

print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

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

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (dist[l] - dist[r]) # (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
print("Yes")

Buggy submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

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

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (dist[x] - dist[y]) # (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
print("Yes")

Buggy submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

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

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(dis[l]) - cost(dis[r]):
      continue
    else:
      print("No")
      exit()
print("Yes")

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

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

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return direct_cost(x) - direct_cost(y)

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(x)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[r])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

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

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  print("{}のコスト:{}".format(x, direct_cost(x)))
  print("{}のコスト:{}".format(y, direct_cost(y)))
  return direct_cost(x) - direct_cost(y)

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(x)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[r])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

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

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return dist[x] - dist[y]

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(x)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[r])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

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

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return dist[x] - dist[y]

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(x)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[rooty])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

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

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return dist[x] - dist[y]

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(x)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[rooty])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dist[x] += direct_cost(par[x])
  par[r] = r
  return r

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return dist[x] - dist[y]

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(x)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[rooty])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")

Buggy submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
par = list(range(n+1))
dist = [0 for _ in range(n+1)]

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dist[x] += direct_cost(par[x])
  par[r] = r
  return r

def direct_cost(x):
  if x == par[x]:
    return 0
  return dist[x] + direct_cost(par[x])
  
def diff(x, y):
  return dist[x] - dist[y]

flag = True
for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が異なってたらとりあえず併合、同じならdifを取って整合性を確かめる
  rootx, rooty = root(l), root(r)
  if rootx != rooty:
    if r != rooty:
      # 直接yにつなげる
      dist[rootx] = d - direct_cost(x)
    else:
      # yの根につなげる
      dist[rootx] = d - (dist[l] - dist[rooty])
    par[rootx] = rooty
  else:
    if d != diff(l, r):
      flag = False
"""
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(par)]
print()
[print("[{}]{}".format(idx, v), end=" ") for idx, v in enumerate(dist)]
print()
"""

print("Yes" if flag else "No")