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:
N, M = map(int, input().split())
l_list = []
r_list = []
d_list = []
for i in range(M):
    l, r, d = map(int, input().split())
    l_list.append(l - 1)
    r_list.append(r - 1)
    d_list.append(d)

position = [float("inf") for _ in range(2*10**6+2)]
for i in range(M):
    l, r, d = l_list[i], r_list[i], d_list[i]

    if position[l] == float("inf") and position[r] == float("inf"):
        position[l] = 0
        position[r] = d
    else:
        if position[l] != float("inf") and position[r] != float("inf"):
            p_r = position[r]
            p_l = position[l]
            if p_r - p_l != d:
                print("No")
                exit()
        elif position[l] != float("inf"):
            p_l = position[l]
            position[r] = position[l] + d
        elif position[r] != float("inf"):
            p_r = position[r]
            position[l] = position[r] - d

print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l_list = []
r_list = []
d_list = []
for i in range(M):
    l, r, d = map(int, input().split())
    l_list.append(l - 1)
    r_list.append(r - 1)
    d_list.append(d)

position = [float("inf") for _ in range(N)]
for i in range(M):
    l, r, d = l_list[i], r_list[i], d_list[i]

    if position[l] == float("inf") and position[r] == float("inf"):
        position[l] = 0
        position[r] = d
    else:
        if position[l] != float("inf") and position[r] != float("inf"):
            p_r = position[r]
            p_l = position[l]
            if p_r - p_l != d:
                print("No")
                exit()
        elif position[l] != float("inf"):
            p_l = position[l]
            position[r] = position[l] + d
        elif position[r] != float("inf"):
            p_r = position[r]
            position[l] = position[r] - d

print("Yes")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from pprint import pprint
import random
from collections import deque, defaultdict
N, M = map(int, input().split())

if M == 0:
    print("Yes")
    exit()

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

# N,M = 100000,200000
# LRD = [[i+10+random.randint(-9,100),i+20+random.randint(-18,200),random.randint(1,300)] for i in range(M)]

# print("run")

# 速めのdfs（非再帰）
graph = defaultdict(lambda: defaultdict(int))
visited = defaultdict(bool)

for L,R,D in LRD:
    graph[L][R] = D
    graph[R][L] = -D
    visited[L] = False
    visited[R] = False

# print("step1")
# pprint(graph)

def xfs(v):
    que = deque()
    que.append((v,0))
    while len(que) > 0:
        i,cnt = que.pop()  # 深さ優先探索
        visited[i] = True
        # print("step3:i",i)
        for n,val in graph[i].items():
            if visited[n] == False:
                # print("if:v,i,n,cnt,val", v,i,n, cnt, val)
                que.append((n, cnt+val))
            elif n == v:
                # print("el:v,i,n,cnt,val", v,i,n, cnt, val)
                if cnt + val != 0:
                    return False

    return True


que2 = deque()
L, _, _ = LRD[0]
que2.append(L)
while len(que2) > 0:
    L = que2.pop()
    # print("step2:L",L)
    if xfs(L):
        for k,v in [(k,v) for k,v in visited.items() if v==False]:
            que2.append(v)
            break
    else:
        # pprint(visited)
        # print("L=",L)
        print("No")
        exit()

# pprint(visited)
print("Yes")

Submission status: Wrong Answer

Solution code:
class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    self.rank=[0]*n
    self.wrong=0

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      if self.weigh(y)-self.weigh(x)!=w:
        self.wrong=1
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)-w
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
        self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)-w
      
      
      
N,M=map(int,input().split())
wuf=WeightsUnionfind(N)
F=0
for m in range(M):
  l,r,d=map(int,input().split())
  wuf.unite(l-1,r-1,d)
if wuf.wrong==1:
  print("No")
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      self.Tree[s1]=s2
      self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      
N,M=map(int,input().split())
List=[[int(i) for i in input().split()] for i in range(M)] 
wuf=WeightsUnionfind(N)
F=0
for l in List:
  wuf.unite(l[0]-1,l[1]-1,l[2])
for l in List:
  if wuf.weigh(l[1]-1)-wuf.weigh(l[0]-1)!=l[2]:
    F=1
    break
if F==1:
  print("No")
else:
  print("Yesa")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    V[R-1] += 1
dist = [-1]*N
for i in range(N):
    if V[i]:
        continue
    S = [i]
    dist[i] = 0
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    V[R-1] += 1
dist = [-1]*N
for i in range(N):
    if V[i] == 1:
        continue
    S = [i]
    dist[i] = 0
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    V[R-1] = 1
dist = [-1]*N
for i in range(N):
    if V[i] == 1:
        continue
    S = [i]
    dist[i] = 0
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    V[R-1] = 1
dist = [-1]*N
for i in range(N):
    if V[i] == 0:
        continue
    S = [i]
    dist[i] = 0
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    V[L-1] = V[R-1] = 1
dist = [-1]*N
for i in range(N):
    if V[i] == 0:
        continue
    S = [i]
    dist[i] = 0
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    E[R-1].append((L-1, -D))
    V[L-1] = V[R-1] = 1
dist = [-1]*N
for i in range(N):
    if V[i] == 0:
        continue
    S = [i]
    dist[i] = 0
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    V[L-1] = V[R-1] = 1
dist = [-1]*N
for i in range(N):
    if V[i] == 0:
        continue
    S = [i]
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
V = [ 0 for _ in range(N)]
for i in range(M):
    L, R, D = map( int, input().split())
    E[L-1].append((R-1,D))
    E[R-1].append((L-1, -D))
    V[L-1] = V[R-1] = 1
dist = [-1]*N
for i in range(N):
    if V[i] == 0:
        continue
    S = [i]
    v = S.pop()
    for u, d in E[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + d
            S.append(u)
ans = "Yes"
for v in range(N):
    for u, d in E[v]:
        if dist[v] + d != dist[u]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Submission status: Wrong Answer

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

class WeightedUnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self.weight = [0] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.weight[a] += self.weight[self.parent[a]]
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b,w):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self.weight[ra] = w - self.weight[a] + self.weight[b]
        else:
            self.parent[rb] = ra
            self.weight[rb] = -w - self.weight[b] + self.weight[a]
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    def diff(self,a,b):
        return self.weight[a] - self.weight[b]

wuf = WeightedUnionFind(N)
for l,r,d in src:
    l,r = l-1, r-1
    if wuf.is_same(l,r):
        wd = wuf.diff(l,r)
        if d != wd:
            print('No')
            exit()
    else:
        wuf.unite(l,r,d)
print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    graph[l-1].append((r-1, d))
    graph[r-1].append((l-1, -d))

x = [-1 for i in range(n)]
for i in range(n):
    if x[i] == -1:
        x[i] = 0
        q = deque([i])
        while q:
            s = q.popleft()
            for node, dist in graph[s]:
                if x[node] == -1:
                    q.append(node)
                    x[node] = x[s] + dist
                elif x[node] != x[s] + dist:
                    print("No")
                    exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# ---
class UnionFind:
    __slots__ = ['nodes', 'weight']

    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size
        self.weight = [0] * size

    # 検索
    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            parent = self.find(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = parent
            return parent

    # 併合
    # def unite(self, x: int, y: int, w: int) -> bool:
    #     root_x = self.find(x)
    #     root_y = self.find(y)
    #     if root_x == root_y:
    #         return False
    #     else:
    #         rank_x = -self.nodes[root_x]
    #         rank_y = -self.nodes[root_y]
    #         if rank_x < rank_y:
    #             self.nodes[root_x] = root_y
    #             self.weight[root_x] = w - self.weight[y] - self.weight[x]
    #         else:
    #             self.nodes[root_y] = root_x
    #             self.weight[root_y] = w - self.weight[x] - self.weight[y]
    #
    #             if rank_x == rank_y:
    #                 self.nodes[root_x] += -1
    #
    #         return True

    # xとyのルートが等しい時: 入力された重みwが正しいかどうかを判定
    # xとyのルートが異なる時: xとyを併合する
    # True: 併合した，False: 何もしなかった，ValueError: 入力された重みに矛盾がある
    def relate(self, x: int, y: int, w: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:  # 入力された重みwに矛盾がないか判定
            # print(x, y, self.weight[x], self.weight[y], w)
            # print(self.get_tree())
            # print(self.weight)
            if self.weight[x] + w == self.weight[y]:
                return False
            raise ValueError
        else:
            rank_x = -self.nodes[root_x]
            rank_y = -self.nodes[root_y]
            if rank_x < rank_y:
                self.nodes[root_x] = root_y
                self.weight[root_x] = w + self.weight[y] - self.weight[x]
            else:
                self.nodes[root_y] = root_x
                self.weight[root_y] = w + self.weight[x] - self.weight[y]

                if rank_x == rank_y:
                    self.nodes[root_x] += -1
            return True

    # UnionFind木の一覧を返す
    def get_tree(self) -> dict:
        tree = {}
        for i, node in enumerate(self.nodes):
            if node < 0:
                if i not in tree.keys():
                    tree[i] = []
            else:
                if self.find(node) in tree.keys():
                    tree[self.find(node)].append(i)
                else:
                    tree[self.find(node)] = [i]

        return tree


N, M = inpl()
uf = UnionFind(N)
relate = uf.relate
try:
    for i in range(M):
        l, r, d = inpl()
        relate(l - 1, r - 1, d)
    else:
        print('Yes')
except ValueError:
    print('No')

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# ---
class UnionFind:
    __slots__ = ['nodes', 'weight']

    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size
        self.weight = [0] * size

    # 検索
    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            parent = self.find(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = parent
            return parent

    # 併合
    # def unite(self, x: int, y: int, w: int) -> bool:
    #     root_x = self.find(x)
    #     root_y = self.find(y)
    #     if root_x == root_y:
    #         return False
    #     else:
    #         rank_x = -self.nodes[root_x]
    #         rank_y = -self.nodes[root_y]
    #         if rank_x < rank_y:
    #             self.nodes[root_x] = root_y
    #             self.weight[root_x] = w - self.weight[y] - self.weight[x]
    #         else:
    #             self.nodes[root_y] = root_x
    #             self.weight[root_y] = w - self.weight[x] - self.weight[y]
    #
    #             if rank_x == rank_y:
    #                 self.nodes[root_x] += -1
    #
    #         return True

    # xとyのルートが等しい時: 入力された重みwが正しいかどうかを判定
    # xとyのルートが異なる時: xとyを併合する
    def relate(self, x: int, y: int, w: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:  # 入力された重みwに矛盾がないか判定
            # print(x, y, w)
            # print(self.get_tree())
            # print(self.get_weight())
            if self.weight[x] + self.weight[y] == w:
                return True
            return False
        else:
            rank_x = -self.nodes[root_x]
            rank_y = -self.nodes[root_y]
            if rank_x < rank_y:
                self.nodes[root_x] = root_y
                self.weight[root_x] = w + self.weight[y] - self.weight[x]
            else:
                self.nodes[root_y] = root_x
                self.weight[root_y] = w + self.weight[x] - self.weight[y]

                if rank_x == rank_y:
                    self.nodes[root_x] += -1
            return True

    # UnionFind木の一覧を返す
    # def get_tree(self) -> dict:
    #     tree = {}
    #     for i, node in enumerate(self.nodes):
    #         if node < 0:
    #             if i not in tree.keys():
    #                 tree[i] = []
    #         else:
    #             if self.find(node) in tree.keys():
    #                 tree[self.find(node)].append(i)
    #             else:
    #                 tree[self.find(node)] = [i]
    #
    #     return tree


N, M = inpl()
uf = UnionFind(N)
relate = uf.relate
for i in range(M):
    l, r, d = inpl()
    if not relate(l - 1, r - 1, d):
        print('No')
        break
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# ---
class UnionFind:
    __slots__ = ['nodes', 'weight']

    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size
        self.weight = [0] * size

    # 検索
    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            parent = self.find(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = parent
            return parent

    # 併合
    # def unite(self, x: int, y: int, w: int) -> bool:
    #     root_x = self.find(x)
    #     root_y = self.find(y)
    #     if root_x == root_y:
    #         return False
    #     else:
    #         rank_x = -self.nodes[root_x]
    #         rank_y = -self.nodes[root_y]
    #         if rank_x < rank_y:
    #             self.nodes[root_x] = root_y
    #             self.weight[root_x] = w - self.weight[y] - self.weight[x]
    #         else:
    #             self.nodes[root_y] = root_x
    #             self.weight[root_y] = w - self.weight[x] - self.weight[y]
    #
    #             if rank_x == rank_y:
    #                 self.nodes[root_x] += -1
    #
    #         return True

    # xとyのルートが等しい時: 入力された重みwが正しいかどうかを判定
    # xとyのルートが異なる時: xとyを併合する
    def relate(self, x: int, y: int, w: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:  # 入力された重みwに矛盾がないか判定
            # print(x, y, w)
            # print(self.get_tree())
            # print(self.get_weight())
            if self.weight[x] + self.weight[y] == w:
                return True
            return False
        else:
            rank_x = -self.nodes[root_x]
            rank_y = -self.nodes[root_y]
            if rank_x < rank_y:
                self.nodes[root_x] = root_y
                self.weight[root_x] = -w + self.weight[y] - self.weight[x]
            else:
                self.nodes[root_y] = root_x
                self.weight[root_y] = w + self.weight[x] - self.weight[y]

                if rank_x == rank_y:
                    self.nodes[root_x] += -1
            return True

    # UnionFind木の一覧を返す
    # def get_tree(self) -> dict:
    #     tree = {}
    #     for i, node in enumerate(self.nodes):
    #         if node < 0:
    #             if i not in tree.keys():
    #                 tree[i] = []
    #         else:
    #             if self.find(node) in tree.keys():
    #                 tree[self.find(node)].append(i)
    #             else:
    #                 tree[self.find(node)] = [i]
    #
    #     return tree


N, M = inpl()
uf = UnionFind(N)
relate = uf.relate
for i in range(M):
    l, r, d = inpl()
    if not relate(l - 1, r - 1, d):
        print('No')
        break
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# ---
class UnionFind:
    __slots__ = ['nodes', 'weight']

    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size
        self.weight = [0] * size

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    # def unite(self, x: int, y: int) -> bool:
    #     x, y = self.get_root(x), self.get_root(y)
    #     if x == y:
    #         return False
    #     else:
    #         rank_x, rank_y = self.nodes[x], self.nodes[y]
    #         if rank_x != rank_y:
    #             if rank_x < rank_y:
    #                 self.nodes[y] = x
    #             else:
    #                 self.nodes[x] = y
    #         else:
    #             self.nodes[x] += -1
    #             self.nodes[y] = x
    #
    #         return True
    #
    # def is_same(self, x: int, y: int) -> bool:
    #     return self.get_root(x) == self.get_root(y)

    def get_weight(self, x: int) -> int:
        self.get_root(x)
        return self.weight[x]

    # def diff(self, x: int, y: int) -> int:
    #     return self.get_weight(y) - self.get_weight(x)

    def relate(self, x: int, y: int, w: int) -> bool:
        rx, ry = self.get_root(x), self.get_root(y)
        if rx == ry:
            if self.get_weight(y) + w == self.get_weight(x):
                return False
            raise ValueError
        else:
            rank_x, rank_y = -self.nodes[rx], -self.nodes[ry]
            if rank_x < rank_y:
                self.nodes[rx] = ry
                self.weight[rx] = w - self.weight[x] + self.weight[y]
            else:
                self.nodes[ry] = rx
                self.weight[ry] = -w - self.weight[y] + self.weight[x]
                if rank_y == rank_x:
                    self.nodes[rx] += -1
            return True


N, M = inpl()
uf = UnionFind(N)
relate = uf.relate

try:
    for i in range(M):
        l, r, d = inpl()
        relate(l - 1, r - 1, d)
    print('Yes')
except ValueError:
    print('No')

Submission status: Wrong Answer

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

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

for l, r, d in lrd:
    if a[l] == a[r]:
        if a[l] == MAX:
            a[l] = 0
            a[r] = d
        elif d != 0:
            print('No')
            exit()
    elif a[l] == MAX:
        a[l] = a[r] - d
    elif a[r] == MAX:
        a[r] = a[l] + d
    elif a[l] + d != a[r]:
        print('No')
        exit()

print('Yes')

Submission status: Wrong Answer

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

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

a[lrd[0][0]] = 0
temp = [lrd[0][0]]
next = []
t = 0
s = 0
max_a = 0
min_a = 0
loop = 0
while 1:
    loop += 1
    if loop > 200000:
        print('Yes')
        exit()
    next = []
    #print("temp", temp)
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
            elif a[t] != s:
                #print(temp, t, a[t])
                print('No')
                exit()

    #print(next)
    if len(next) == 0:
        target = 0
        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                target = lrd[i][0]
                check = 1
        if check == 0:
            break
        a[target] = 0
        next = [target]

    #print(next)
    temp = [] + list(set(next))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
for i in range(m):
  input()

print('Yes')

Submission status: Wrong Answer

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

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

a[lrd[0][0]] = 0
temp = [lrd[0][0]]
next = []
t = 0
s = 0
max_a = 0
min_a = 0
while 1:
    next = []
    #print("temp", temp)
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
            elif a[t] != s:
                print(temp, t, a[t])
                print('No')
                exit()

    #print(next)
    if len(next) == 0:
        target = 0
        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                target = lrd[i][0]
                check = 1
        if check == 0:
            break
        a[target] = 0
        next = [target]

    #print(next)
    temp = [] + list(set(next))

print('Yes')

Submission status: Wrong Answer

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

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

a[lrd[0][0]] = 0
temp = [lrd[0][0]]
next = []
t = 0
s = 0
max_a = 0
min_a = 0
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
                if a[t] > max_a:
                    max_a = a[t]
                elif a[t] < min_a:
                    min_a = a[t]
                if max_a - min_a > 10 ** 9:
                    print('No')
                    exit()
            elif a[t] != s:
                print('No')
                exit()
    if len(next) == 0:

        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                next.append(lrd[i][0])
                a[lrd[i][0]] = 0
                check = 1
        if check == 0:
            break

    temp = [] + next

print('Yes')

Submission status: Wrong Answer

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

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

a[lrd[0][0]] = 0
temp = [lrd[0][0]]
next = []
t = 0
s = 0
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
            elif a[t] != s:
                print('No')
                exit()
    if len(next) == 0:
        #print(temp)
        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                next.append(lrd[i][0])
                a[lrd[i][0]] = 0
                check = 1
        if check == 0:
            break

    temp = [] + next

print('Yes')