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:
class WeightedUnionFind(object):#インデックスに注意
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        #根からの距離
        self.weight=[0 for _ in range(size)]

    def find(self, x):#根を探す
        if self.parent[x] == x:#根なら返す
            return x
        else:
            self.weight[x]+=self.weight[self.parent[x]]#親のvalueを加えていく
            self.parent[x] = self.find(self.parent[x])#一度調べた値を根につなぎ直す
            return self.parent[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.weight[x] + self.weight[y]
        else:
            self.parent[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.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: Wrong Answer

Solution code:
#ABC087-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())

class WeightedUnionFind:
    def __init__(self, size):
        """
        :param collections.Iterable nodes:
        """
        self._parents = [i for i in range(size)]
        self._ranks = [0 for _ in range(size)]
        self._sizes = [1 for _ in range(size)]
        # 直近の親からの重み。root なら 0
        self._weights = [0 for _ in range(size)]
 
    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
 
        # rank が小さい方が下
        if self._ranks[rx] > self._ranks[ry]:
            # x が root
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            # root 間の重みに変換
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            # y が root
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            # root 間の重みに変換
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1
 
    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root
 
    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]
 
    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]

Submission status: Wrong Answer

Solution code:
queue=[]
N,M=map(int,input().split())
NE=9223372036854775807
mp=[NE]*(N+1)
lst=[[] for _ in range(N+1)]
for _ in range(M):
    L,R,D = map(int, input().split())
    lst[L].append((L,R,D))
    lst[R].append((L,R,D))

isinit = True
def check(L, R, D):
    if mp[L] == NE and mp[R] == NE:
        return 1
    elif mp[L] == NE:
        mp[L] = mp[R]-D
    elif mp[R] == NE:
        mp[R] = mp[L]+D
    else:
        if mp[L]+D != mp[R]:
            print("NO")
            exit()

def check_list(ls, checking):
    while len(ls):
        L,R,D = ls.pop()
        if L == checking:
            check(L,R,D)
            if len(lst[R]):
                queue.append(R)
        else:
            check(L,R,D)
            if len(lst[L]):
                queue.append(L)

# print(lst)
for i in range(1, N+1):
    if mp[i] == NE: mp[i] = 0
    check_list(lst[i], i)

    while(len(queue) > 0):
        num = queue.pop()
        check_list(lst[num], num)
# print(mp)
print("YES")

Submission status: Wrong Answer

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))
	inr[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 None:
			pos[r] = pos[l] + d
			det.add(r)
		elif pos[r] != pos[l] + d:
			ans = "No"
			break

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

print(ans)

Submission status: Wrong Answer

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))
	inr[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 None:
			pos[r] = pos[l] + d
			det.add(r)
		elif pos[r] != pos[l] + d:
			ans = "No"
			break

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

print(ans)

Submission status: Wrong Answer

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

fi=True
inl=[[] for _ in range(N+1)]
inr=[[] for _ in range(N+1)]
pos=[-1 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] != -1:
			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] != -1:
			if pos[l] != pos[r] - d:
				ans = "No"
				break
		else:
			pos[l] = pos[r] - d
			det.add(l)

print(ans)

Submission status: Wrong Answer

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

ans="Yes"
first=True
data=[-1 for _ in range(N+1)]

for _ in range(M):
	l,r,d=map(int, input().split())
	if first:
		data[l] = 0
		first = False
	if data[r] > -1 and data[r] != data[l] + d:
		ans = "No"
		break
	data[r] = data[l] + d

print(ans)

Submission status: Wrong Answer

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[1] = 1

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

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

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]
    d = self.diff[x]
    if px == x:
      return d, px
    else:
      rd, rx = self.root(px)
      self.parent[x] = rx
      self.diff[x] = d + rd
      return d + rd, rx
  
  def unite(self, x, y, d):
    dx, rx = self.root(x)
    dy, ry = self.root(y)
    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: Wrong Answer

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

roots = [(i,0) for i in range(N+1)] #(root, distance_from_i_to_root)

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return (a,0)
  else:
    r, d = find_root(roots[a][0])
    roots[a] = (r, roots[a][1] + d)
  return roots[a]

def unite(l, r, d, roots=roots):
  root_l, d_l = find_root(l)
  root_r, d_r = find_root(r)
  if root_l == root_r:
    if d_l == d + d_r:
      return True
    else:
      return False
  else:
    roots[root_l] = (root_r, d + d_r)
    return True

for l,r,d in LRD:
  if not unite(l,r,d):
    print('No')
    break
else:
  print('Yes')

Submission status: Wrong Answer

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

roots = [(i,0) for i in range(N+1)]

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return (a,0)
  else:
    r, d = find_root(roots[a][0])
    roots[a] = (r, roots[a][1] + d)
  return roots[a]

def unite(l, r, d, roots=roots):
  root_l, d_l = find_root(l)
  root_r, d_r = find_root(r)
  if root_l == root_r:
    if d_l != d + d_r:
      return False
    return True
  else:
    roots[root_l] = (r, d - d_r)
    return True

for l,r,d in LRD:
  if not unite(l,r,d):
    print('No')
    break
else:
  print('Yes')

Submission status: Wrong Answer

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

roots = [(i,0) for i in range(N+1)]

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return (a,0)
  else:
    r, d = find_root(roots[a][0])
    roots[a] = (r, roots[a][1] + d)
  return roots[a]

def unite(l, r, d, roots=roots):
  root_l, d_l = find_root(l)
  root_r, d_r = find_root(r)
  if root_l == root_r:
    if d_l != d + d_r:
      return False
    return True
  else:
    roots[root_l] = (r, d - d_r)
    return True

for l,r,d in LRD:
  if not unite(l,r,d):
    print('No')
    break
print('Yes')

Submission status: Wrong Answer

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[rx] = ry
        d2p[rx] = d
        #print(par, d2p,"noz")
        return True
    else:
        if dx - dy != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

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

for i in range(0, m):
    l[i], r[i], d[i] = [int(j) for j 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: Wrong Answer

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 dx - dy != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

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

for i in range(0, m):
    l[i], r[i], d[i] = [int(j) for j 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: Wrong Answer

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[y] - self.weight[x]


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

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

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

        elif UF.is_same(l, r) and UF.diff(r, l) != d:
            return 'No'

        else:
            continue

    return 'Yes'


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

Submission status: Wrong Answer

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, M = map(int, input().split())
    UF = UnionFind(N)

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

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

        elif UF.is_same(l, r) and UF.diff(r, l) != d:
            return 'No'

        else:
            continue

    return 'Yes'


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

Submission status: Wrong Answer

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, M = map(int, input().split())
    UF = UnionFind(N)

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

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

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

    return 'Yes'


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

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
lrd = [[int(item) for item in input().split()] for _ in range(m)]
 
class DisjointSet:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.dist = [0] * (n+1)
    self.rank = [0] * (n+1)
 
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      y = self.find(self.par[x])
      self.dist[x] += self.dist[self.par[x]]
      self.par[x] = y
      return self.par[x]
    
  def union(self, x, y, d):
    dx = self.dist[x]
    dy = self.dist[y]
    x = self.find(x)
    y = self.find(y)
    if (x == y):
      return False
    if self.rank[x] < self.rank[y]:
      self.dist[x] = d - dx + dy
      self.par[x] = y
    else:
      self.dist[y] = d -dy + dx
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def diff(self, x, y):
    return self.dist[y] - self.dist[x]

harmony = True
djs = DisjointSet(n)
for l, r, d in lrd:
  djs.union(l,r,d)
  if djs.diff(l,r) != d:
    harmony = False
    
if harmony:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
lrd = [[int(item) for item in input().split()] for _ in range(m)]

class DisjointSet:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.dist = [0] * (n+1)
    self.rank = [0] * (n+1)

  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.dist[x] += self.dist[self.par[x]]
      self.par[x] = self.find(self.par[x])
      return self.par[x]
    
  def union(self, x, y, d):
    dx = self.dist[x]
    dy = self.dist[y]
    x = self.find(x)
    y = self.find(y)
    if (x == y):
      return False
    if self.rank[x] < self.rank[y]:
      self.dist[x] = d + dy - dx
      self.par[x] = y
    else:
      self.dist[y] = -d - dy + dx
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def diff(self, x, y):
    return self.dist[x] - self.dist[y]

harmony = True
djs = DisjointSet(n)
for l, r, d in lrd:
  if djs.issame(l,r):
    if djs.diff(l,r) != d:
      harmony = False
  else:
    djs.union(l,r,d)
    
if harmony:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
lrd = [[int(item) for item in input().split()] for _ in range(m)]

class DisjointSet:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.dist = [0] * (n+1)
    self.rank = [0] * (n+1)

  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.dist[x] += self.dist[self.par[x]]
      self.par[x] = self.find(self.par[x])
      return self.par[x]
    
  def union(self, x, y, d):
    dx = self.distance(x)
    dy = self.distance(y)
    x = self.find(x)
    y = self.find(y)
    if (x == y):
      return False
    if self.rank[x] < self.rank[y]:
      self.dist[x] = d + dy - dx
      self.par[x] = y
    else:
      self.dist[y] = -d - dy + dx
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
   
  def distance(self, x):
    self.find(x)
    return self.dist[x]
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def diff(self, x, y):
    return self.distance(x) - self.distance(y)

harmony = True
djs = DisjointSet(n)
for l, r, d in lrd:
  djs.union(l,r,d)
  if djs.diff(l,r) != d:
    harmony = False
    
if harmony:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
lrd = [[int(item) for item in input().split()] for _ in range(m)]

class DisjointSet:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.dist = [0] * (n+1)
    self.rank = [0] * (n+1)

  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.dist[x] += self.distance(self.par[x])
      self.par[x] = self.find(self.par[x])
      return self.par[x]
    
  def union(self, x, y, d):
    dx = self.distance(x)
    dy = self.distance(y)
    x = self.find(x)
    y = self.find(y)
    if (x == y):
      return False
    if self.rank[x] < self.rank[y]:
      self.dist[x] = d + dy - dx
      self.par[x] = y
    else:
      self.dist[y] = d - dy + dx
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
   
  def distance(self, x):
    self.find(x)
    return self.dist[x]
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def diff(self, x, y):
    return self.distance(y) - self.distance(x)

harmony = True
djs = DisjointSet(n)
for l, r, d in lrd:
  djs.union(l,r,d)
  if djs.diff(l,r) != d:
    harmony = False
    
if harmony:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
lrd = [[int(item) for item in input().split()] for _ in range(m)]

class DisjointSet:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.dist = [0] * (n+1)
    self.rank = [0] * (n+1)

  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.dist[x] += self.dist[self.par[x]]
      self.par[x] = self.find(self.par[x])
      return self.par[x]
    
  def union(self, x, y, d):
    dx = self.dist[x]
    dy = self.dist[y]
    x = self.find(x)
    y = self.find(y)
    if (x == y):
      return False
    if self.rank[x] < self.rank[y]:
      self.dist[x] = d - dx + dy
      self.par[x] = y
    else:
      self.dist[y] = d -dy + dx
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def diff(self, x, y):
    return self.dist[y] - self.dist[x]

harmony = True
djs = DisjointSet(n)
for l, r, d in lrd:
  djs.union(l,r,d)
  if djs.diff(l,r) != d:
    harmony = False
    
if harmony:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
point = ["Yet" for i in range(n+1)]
ans = "Yes"
for i in range(m):
    l,r,d = map(int,input().split())
    if point[l] == "Yet" and point[r] == "Yet":
        point[l] = 0
        point[r] = d
    elif point[l] == "Yet":
        point[l] = point[r] - d
    elif point[r] == "Yet":
        point[r] = point[l] + d
    else:
        if point[l] + d != point[r]:
            ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[False]*(n+1)
t=[0]*(n+1)
for i in range(m):
    l,r,d=map(int,input().split())
    if s[l]:
        if s[r]:
            if t[r]-t[l]!=d:
                print("No")
                break
        else:
            t[r]=t[l]+d
            s[r]=True
    else:
        if s[r]:
            t[l]=t[r]-d
            s[l]=True
        else:
            t[r]=t[l]+d
            s[l]=True
            s[r]=True
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[False]*(n+1)
t=[0]*(n+1)
for i in range(m):
    l,r,d=map(int,input().split())
    if s[l]:
        if s[r]:
            if t[r]-t[l]!=d:
                print("No")
        else:
            t[r]=t[l]+d
            s[r]=True
    else:
        if s[r]:
            t[l]=t[r]-d
            s[l]=True
        else:
            t[r]=t[l]+d
            s[l]=True
            s[r]=True
else:
    print("Yes")

Submission status: Wrong Answer

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[0])

arr = [0]+[" "]*(n)

for i in range(m):
    l,r,d = q[i]
    if arr[l] == " ":
        arr[l] = 0
    if arr[r] == " ":
        arr[r] = arr[l]+d
    elif arr[r] == arr[l]+d:
        continue
    else:
        print("No")
        exit(0)
print("Yes")

Submission status: Wrong Answer

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

tree = [None] * (N + 1)

def parent(n):
    if tree[n] is None:
        return [n, 0]
    d = distance_to_root(n)
    p = parent(tree[n][0])
    p[1] = d
    tree[n] = p
    return p

def distance_to_root(n):
    if tree[n] is None:
        return 0
    d = distance_to_root(tree[n][0])
    return d + tree[n][1]

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def weight(x):
        root(x)
        return d[x]
    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    d = [0 for i in range(n)]
    for i in range(m):
        x,y,w = LI()
        x -= 1
        y -= 1
        if same(x,y):
            if weight(y)-weight(x) != w:
                print("No")
                quit()
        else:
            unite(x,y,w)
    print("Yes")
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()