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: Runtime Error

Solution code:
class WeightedUnionFind
  def initialize(n)
    @parent = (0...n).to_a # 親の番号
    @rank = Array.new(n, 0) # 木の深さ
    @diff_weight = Array.new(n, 0) # 親との重みの差
  end

  def root(x)
    return x if @parent[x] == x
    r = root(@parent[x])
    @diff_weight[x] += @diff_weight[@parent[x]]
    @parent[x] = r
    return r
  end

  def weight(x)
    root(x)
    return @diff_weight[x]
  end

  def same?(x, y)
    root(x) == root(y)
  end

  def diff(x, y)
    # x と y とが同じグループにいるとき、weight(y) - weight(x) を返す
    # 同じグループでないならnil
    return nil if !same?(x, y)
    return weight(y) - weight(x)
  end

  def merge(x, y, w)
    # weight(y) - weight(x) = wとなるように結合
    w += weight(x)
    w -= weight(y)
    x, y = root(x), root(y)
    return false if x == y
    if @rank[x] < @rank[y]
      x, y = y, x
      w = -w
    end
    @rank[x] += 1 if @rank[x] == @rank[y]
    @parent[y] = x
    @diff_weight[y] = w
    return true
  end
end



N,M=gets.split.map(&:to_i)
uf= WeightedUnionFind.new(N)
M.times do
  l, r, d = gets.split.map(&:to_i)
  if uf.same?(l-1, r-1)
    if uf.diff(l-1, r-1) != d
      puts 'No'
      exit(0)
    end
  end
  uf.merge(l-1, r-1, d)
end

puts 'Yes'

Submission status: Runtime Error

Solution code:
II.c=-1

N,M = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(M) ]

up = [ set([]) for i in range(N)]
dw = [ set([]) for i in range(N)]

for l,r,d in li:
  dw[l-1].add(r-1)
  up[r-1].add(l-1)

S = []
for n in range(N):
  if ( len(up[n])==0 ):
    S.append(n)
L = []
for i in range(N+M):

  if ( len(S)==0 ):
    break
  n = S.pop()
  L.append(n)
  for r in dw[n]:
    up[r].discard(n)
    if ( len(up[r]) == 0 ):
      S.append(r)
  dw[n]=set()

BREAK=False
if (sum([len(s) for s in up])>0):
    BREAK=True

dwl = [ set([]) for i in range(N)]
for l,r,d in li:
  dwl[l-1].add((r-1,d))

dis = [-1]*N

for n in L:
  if (BREAK):
    break
  if (dis[n]==-1):
    dis[n]=0
  for r,d in dwl[n]:
    if (dis[r]==-1):
        dis[r]=dis[n]+d
    else:
        if not (dis[r]==dis[n]+d):
            BREAK=True
            break
if (BREAK):
    print ("No")
else:
    print ("Yes")

Submission status: Runtime Error

Solution code:
class WeightedUnionFind(object):#インデックスに注意
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        #根からの距離
        self.diff_weight=[0 for _ in range(size)]

    def find(self, x):#根を探す
        if self.parent[x] == x:#根なら返す
            return x
        else:
            self.diff_weight[x] += self.diff_weight[self.parent[x]]
            self.parent[x] = self.find(self.parent[x])#一度調べた値を根につなぎ直す
            return self.parent[x]
    def weight(self, x):
        self.find(x);
        return self.diff_weight[x]
    

    def unite(self, x, y, w):#要素、要素、その間のweight
        #根を探す
        rx = self.find(x)
        ry = self.find(y)
        if x == y:#すでに同じグループにいれば何もしない
            return

        if self.rank[rx] < self.rank[ry]:#yの方が高い場合
            self.parent[rx] = ry#yの根にxの根をつなぐ
            
            #xの根のweightをxとyの間のweightがwになるように更新
            self.weight[rx]=w - self.diff_weight[x] + self.diff_weight[y]
        else:
            self.parent[ry] = rx
            self.diff_weight[ry] = -w - self.diff_weight[y] + self.diff_weight[x]
            if self.rank[rx] == self.rank[ry]:#同じ高さの時
                self.rank[x] += 1#片方の高さを＋１する
        #終わった時点では根ではない点のweightは更新されていないことに注意

    def same(self, x, y):#同じ集合に属するか？
        return self.find(x) == self.find(y)
    # xからyへのコスト
    def diff(self, x, y):
        if self.same(x, y):
            return self.weight(x) - self.weight(y)
n, m=map(int, input().split())
U=WeightedUnionFind(n)
def C(U):
    for i in range(m):
        l, r, d = map(int, input().split())
        if U.same(l-1, r-1):
            if U.diff(l-1, r-1)!=d:
                return False
        else:
            U.unite(l-1, r-1, d)
    return True
if C(U):
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(65536)

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

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

for _ in range(M):
	l,r,d=map(int, input().split())
	path[l].append((r,+d))
	path[r].append((l,-d))

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

def walk(i, c):
	if cost[i] is None:
		cost[i] = c
		for j,d in path[i]:
			if not walk(j, c+d):
				return False
	return cost[i] == c

ans = "Yes"

for i in range(1, N+1):
	if cost[i] is None and not walk(i, 0):
		ans = "No"
		break

print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int, input().split())

fi=True
inl=[[] for _ in range(N+1)]
inr=[[] for _ in range(N+1)]
pos=[None for _ in range(N+1)]
det=set()

for _ in range(M):
	l,r,d=map(int, input().split())
	inl[l].append((l,r,d))
	inl[r].append((l,r,d))

	if fi:
		fi=False
		det.add(l)
		det.add(r)
		pos[l]=0
		pos[r]=d

ans = "Yes"

while len(det) > 0 and ans == "Yes":
	p = det.pop()

	for l,r,d in inl[p]:
		if pos[r] is not None:
			if pos[r] != pos[l] + d:
				ans = "No"
				break
		else:
			pos[r] = pos[l] + d
			det.add(r)

	for l,r,d in inr[p]:
		if pos[l] is not None:
			if pos[l] != pos[r] - d:
				ans = "No"
				break
		else:
			pos[l] = pos[r] - d
			det.add(l)

print(ans)

Submission status: Runtime Error

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

data = sorted(data)

INF = 10 ** 9
L = [INF] * (N + 1)
L[data[0][0]] = 0

for l, r, d in data:
    if L[r] == INF:
        L[r] = L[l] + d
    else:
        if L[l] == INF:
            L[l] = L[r] - d
        else:
            if L[r] != L[l] + d:
                print('No')
                exit()
print('Yes')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
LRD = (map(int, input().split()) for _ in range(M))


class UF:
  def __init__(self, n):
    self.parent = [i for i in range(n+1)]
    self.diff = [0 for i in range(n+1)]
    
  def root(self, x):
    px = self.parent[x]
    if px == x:
      return 0, px
    else:
      rd, rx = self.root(px)
      self.parent[x] = rx
      self.diff[x] += rd
      return self.diff[x], rx
  
  def unite(self, x, y, d):
    dx, rx = self.root(x)
    dy, ry = self.root(y)
    print(self.parent, self.diff)
    if rx == ry:
      if d != dy - dx:
        return False
    else:
      self.parent[y] = x
      self.diff[y] = d
    return True

uf = UF(N)
for l, r, d in LRD:
  if l > r:
    l, r, d = r, l, -d
  b = uf.unite(l, r, d)
  if not b:
    print('No')
    break
else:
  print('Yes')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)

n, m = [int(i) for i in input().split(" ")]

par = [i for i in range(0, n + 1)]
d2p = [0 for i in range(0, n + 1)]

def root(x):
    global par
    global d2p
    if par[x] == x:
        return (x, 0)
    else:
        r = root(par[x])
        par[x] = r[0]
        d2p[x] += r[1]
        #print(par, d2p)
        return (r[0], d2p[x])


def unite(x, y, d):
    global par
    global d2p
    #print(x, y, d)
    rx, dx = root(x)
    ry, dy = root(y)
    if rx != ry:
        par[x] = y
        d2p[x] = d
        #print(par, d2p,"noz")
        return True
    else:
        if dy - dx != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

l = [0] * n
r = [0] * n
d = [0] * n

for i in range(0, m):
    l[i], r[i], d[i] = [int(i) for i in input().split(" ")]

f = True
for i in range(0, m):
    if not unite(l[i], r[i], d[i]):
        f = False
        break

if f and max(d2p) <= 10**9:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split(" ")]

par = [i for i in range(0, n + 1)]
d2p = [0 for i in range(0, n + 1)]

def root(x):
    global par
    global d2p
    if par[x] == x:
        return (x, 0)
    else:
        r = root(par[x])
        par[x] = r[0]
        d2p[x] += r[1]
        #print(par, d2p)
        return (r[0], d2p[x])


def unite(x, y, d):
    global par
    global d2p
    #print(x, y, d)
    rx, dx = root(x)
    ry, dy = root(y)
    if rx != ry:
        par[x] = y
        d2p[x] = d
        #print(par, d2p,"noz")
        return True
    else:
        if abs(dx - dy) != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

l = [0] * n
r = [0] * n
d = [0] * n

for i in range(0, m):
    l[i], r[i], d[i] = [int(i) for i in input().split(" ")]

f = True
for i in range(0, m):
    if not unite(l[i], r[i], d[i]):
        f = False
        break

if f and max(d2p) <= 10**9:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
import sys

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  # The number of nodes under the target node.
        self.weight = [0] * (n+1)  # Distance from the root

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unite(self, x, y, w=0):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
            self.size[ry] += self.size[rx]
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.root[ry] = rx
            self.size[rx] += self.size[ry]
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    UF = UnionFind(N)

    for _ in range(M):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1

        if not is_same(l, r):
            UF.unite(l, r, d)

        elif is_same(l, r) and diff(r, l) == d:
            continue
        else:
            return 'No'

    return 'Yes'


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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())

q = []

for i in range(m):
    l,r,d = map(int,input().split())
    if l < r:
        q.append((l,r,d))
    else:
        q.append((r,l,-d))
q.sort(key=lambda x:x[:2],reverse=True)

#print(q)
arr = [0]+[" "]*(n)

while q!=[]:
    l,r,d = q[-1]
    if arr[l] == " ":
        flag = False
        for j in range(len(q)-1,-1,-1):
            if q[j][0]==l:
                if arr[q[j][1]]!=" ":
                    arr[l] = arr[q[j][1]] - arr[q[j][2]]
                    flag = True
                    break
            else:
                break
        if not flag:
            arr[l] = 0
    if arr[r] == " ":
        arr[r] = arr[l]+d
    elif arr[r] !=arr[l]+d:
        print("No")
        exit(0)
    q.pop()
print("Yes")

Submission status: Runtime Error

Solution code:
import sys

def update(L, R, D, d={}):
    if L in d:
        if R in d[L]:
            if d[L][R] == D:
                return d
            else:
                d['ans'] = False
        else:
            d[L][R] = D
            for r in d[L]:
                newD = D - d[L][r]
                update(r, R, newD)
            return d
    else:
        d[L] = {}
        d[L][R] = D
        return d




def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    d = {}
    ans = 'Yes'
    for _ in range(M):
        L, R, D = map(int, input().split())
        d = update(L, R, D, )
        if 'ans' in d:
            ans = 'No'
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N + 1)]
for _ in range(M):
    l, r, d = map(int, input().split())
    E[l].append((r, d))
    E[r].append((l, -d))
INF = 10**10
dp = [INF for i in range(N + 1)]


def dfs(i):
    for r, d in E[i]:
        if dp[r] == INF:
            dp[r] = dp[i] + d
            if not dfs(r):
                return False
        elif dp[r] != dp[i] + d:
            return False
    return True


for i in range(1, N + 1):
    if dp[i] == INF:
        dp[i] = 0
        if not dfs(i):
            print('No')
            break
else:
    print('Yes')

Submission status: Runtime Error

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

class Unionfind:
    __slots__ = ["nodaes","diff_weight"]

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x
    
    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        rank_x = -self.nodes[x]; rank_y = -self.nodes[y]
        if rank_x < rank_y:
            x, y = y, x; w = -w
        if rank_x == rank_y:
            self.nodes[x] -= 1
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]
    
    def diff(self, x, y):
        return self.weight(y) - self.weight(x)
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def rank(self, x):
        return -self.nodes[self.root(x)]
    
N,M = map(int,input().split())
uf = Unionfind(N)
ans = "Yes"
for _ in range(M):
    L, R, D = map(int,input().split())
    L -= 1; R -= 1
    uf.unite(L, R, D)   
    if uf.diff(L, R) != D:
        ans = "No"
        break
print(ans)

Submission status: Runtime Error

Solution code:
#import matplotlib.pyplot as plt
#import networkx as nx

n, m = map(int, input().split())
D = [list(map(int, input().split())) for i in range(m)]

G = [[0, 0, []] for i in range(n+1)]


#print(G.nodes())
for i in range(m) :
    G[D[i][0]][2].append([D[i][1], D[i][2]])
    G[D[i][1]][2].append([D[i][0], -D[i][2]])

global no
no = 0

def d(a):
    G[a][1] = 1
    A = []
    #print(len(G[a][2]))
    #print(G[a][2][0][0])
    for j in range(len(G[a][2])) :
        i = G[a][2][j][0]
        #print(set(list(nx.all_neighbors(G, a))))
        #print("{} {}".format(a,i))
        if G[i][1] == 0 :
            A.append(i)
            G[i][0] = G[a][0] + G[a][2][j][1]
            G[i][1] = 1
        else :
            #print("{} {} {}".format(G[i][0],G[a][0],G[a][2][j][1]))
            if G[i][0] != G[a][0] + G[a][2][j][1] :
                #print("A")
                global no
                no = 1
                #print("{} {}".format("no",no))
    for i in A :
        d(i)

for i in range(1,n+1):
    if G[i][1] == 0 :
        d(i)
        
if no == 1 :
    print("No")
else :
    print("Yes")

Submission status: Runtime Error

Solution code:
#import matplotlib.pyplot as plt
import networkx as nx

n, m = map(int, input().split())
D = [list(map(int, input().split())) for i in range(m)]

G = [[0, 0, []] for i in range(n+1)]


#print(G.nodes())
for i in range(m) :
    G[D[i][0]][2].append([D[i][1], D[i][2]])
    G[D[i][1]][2].append([D[i][0], -D[i][2]])

global no
no = 0

def d(a):
    G[a][1] = 1
    A = []
    #print(len(G[a][2]))
    #print(G[a][2][0][0])
    for j in range(len(G[a][2])) :
        i = G[a][2][j][0]
        #print(set(list(nx.all_neighbors(G, a))))
        #print("{} {}".format(a,i))
        if G[i][1] == 0 :
            A.append(i)
            G[i][0] = G[a][0] + G[a][2][j][1]
            G[i][1] = 1
        else :
            #print("{} {} {}".format(G[i][0],G[a][0],G[a][2][j][1]))
            if G[i][0] != G[a][0] + G[a][2][j][1] :
                #print("A")
                global no
                no = 1
                #print("{} {}".format("no",no))
    for i in A :
        d(i)

for i in range(1,n+1):
    if G[i][1] == 0 :
        d(i)
        
if no == 1 :
    print("No")
else :
    print("Yes")

Submission status: Runtime Error

Solution code:
#import matplotlib.pyplot as plt
import networkx as nx

n, m = map(int, input().split())
D = [list(map(int, input().split())) for i in range(m)]

G = nx.DiGraph()
for i in range(n) :
    G.add_node(i+1, seisu = 0, houmon = 0)

#print(G.nodes())
for i in range(m) :
    G.add_edge(D[i][0], D[i][1], weight=D[i][2])
    G.add_edge(D[i][1], D[i][0], weight=-D[i][2])

global no
no = 0

def d(a):
    G.nodes[a]["houmon"] = 1
    A = []
    for i in set(list(nx.all_neighbors(G, a))) :
        #print(set(list(nx.all_neighbors(G, a))))
        #print("{} {}".format(a,i))
        if G.nodes[i]["houmon"] == 0 :
            A.append(i)
            G.nodes[i]["seisu"] = G.nodes[a]["seisu"] + G.edges[a, i]["weight"]
            G.nodes[i]["houmon"] = 1
        else :
            #print("{} {} {}".format(G.nodes[i]["seisu"],G.nodes[a]["seisu"],G.edges[a, i]["weight"]))
            if G.nodes[i]["seisu"] != G.nodes[a]["seisu"] + G.edges[a, i]["weight"] :
                #print("A")
                global no
                no = 1
                #print("{} {}".format("no",no))
    for i in A :
        d(i)

for i in range(1,n+1):
    if G.nodes[i]["houmon"] == 0 :
        d(i)
        
if no == 1 :
    print("No")
else :
    print("Yes")

Submission status: Runtime Error

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

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        parent = nodes[x]
        # 経路圧縮:再帰的に根を調べてその過程で通った要素は全て根に直接つなぎ直す
        nodes[x] = root(nodes[x])
        # 親の重みの累積和をとる. これがxを根に直接繋いだ時の重みになる
        weight[x] += weight[parent]
        return nodes[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    #根ノードは木の高さを表す(負数で表していることに注意)
    rank_x = -nodes[root_x]; rank_y = -nodes[root_y]
    if rank_x >= rank_y:
        root_l = root_x; root_s = root_y
        l = x; s = y
    else:
        root_l = root_y; root_s = root_x
        l = y; s = x
        w *= -1
    # 繋いだ分だけ木を高くする
    nodes[root_l] += nodes[root_s]
    # 低い木を高い木に繋げる
    nodes[root_s] = root_l
    # 繋ぎ直す時の重みの変更
    weight[root_s] = w - weight[s] + weight[l]

# 根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xからyへの重み
def diff(x,y):
    return weight[y] - weight[x]

# ノードは-1で初期化, Nは頂点数
nodes = [-1]*N
# ウェイトは0で初期化, Nは頂点数
weight = [0]*N

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)

for L,R,D in info:
    L -= 1; R -= 1
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    for elem in G[i]:
        if field[elem[0]] is not None:
            if field[elem[0]] != field[i]+elem[1]:
                return False
            continue
        else:
            field[elem[0]] = field[i]+elem[1]
            dfs(elem[0])
    return True


for i in range(1, N+1):
    if field[i] is None:
        field[i] = 0
        if not dfs(i):
            print('No')
            exit()
print('Yes')

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")

Submission status: Runtime Error

Solution code:
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")