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())
LRD = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for L,R,D in LRD:
    E[L-1][R-1] = D
    E[R-1][L-1] = -D

V = [-1]*N
breakFlg = False
for i in range(N):
    if V[i]!=-1:continue
    V[i] = 0
    q = [i]
    while q:
        j = q.pop()
        v = V[j]
        for k,d in E[j].items():
            if V[k] == -1:
                V[k] = v+d
                q.append(k)
ans = True
for l,e in enumerate(E):
    for r,d in e.items():
        ans = ans and V[r]-V[l]==d
    if not ans:break
print("Yes" if ans else "No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]

from collections import deque
def topological_sort(graph: list, n_v: int) -> list:
    res = []
    indegree = [0] * n_v

    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque()
    for i in range(n_v):
        if indegree[i] == 0:
            cand.append(i)

    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res


def is_dag(graph: list, n_v: int):
    ts = topological_sort(graph, n_v)
    return len(ts) == n_v


n, m = map(int, input().split())
graph = defaultdict(list)
graph2 = defaultdict(list)
edges = []
l_nodes = set()
r_nodes = set()
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges.append((l, r, d))
    graph[l].append((d, r))
    graph2[r].append((d, l))

    l_nodes.add(l)
    r_nodes.add(r)


if m == 0:
    print("Yes")
elif not is_dag(graph, n):
    print("No")
else:
    x = l_nodes - r_nodes

    dist = dijkstra(graph, n, list(x)[0])
    possible = True
    for l, r, d in edges:
        if dist[l] != float('inf') and dist[r] != float('inf') and d != abs(dist[l] - dist[r]):
            possible = False
            break

    if possible:
        x = r_nodes - l_nodes

        dist = dijkstra(graph2, n, list(x)[0])
        possible = True
        for l, r, d in edges:
            if dist[l] != float('inf') and dist[r] != float('inf') and d != abs(dist[l] - dist[r]):
                possible = False
                break
        if possible:
            print("Yes")
        else:
            print("No")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]

from collections import deque
def topological_sort(graph: list, n_v: int) -> list:
    res = []
    indegree = [0] * n_v

    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque()
    for i in range(n_v):
        if indegree[i] == 0:
            cand.append(i)

    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res


def is_dag(graph: list, n_v: int):
    ts = topological_sort(graph, n_v)
    return len(ts) == n_v


n, m = map(int, input().split())
graph = defaultdict(list)
edges = []
l_nodes = set()
r_nodes = set()
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges.append((l, r, d))
    graph[l].append((d, r))
    l_nodes.add(l)
    r_nodes.add(r)


if m == 0:
    print("Yes")
elif not is_dag(graph, n):
    print("No")
else:
    x = l_nodes - r_nodes

    dist = dijkstra(graph, n, list(x)[0])
    possible = True
    for l, r, d in edges:
        if d != abs(dist[l] - dist[r]):
            possible = False
            break

    if possible:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc087/tasks/arc090_b


def solve(n, query):
    for l, r, d in query:
        if is_same(l, r):
            if d != diff(l, r):
                return 'No'
        else:
            unite(l, r, d)
    return 'Yes'


def unite(x, y, w):
    w += diff_weight[x]-diff_weight[y]
    rt_x = find(x)
    rt_y = find(y)

    if rt_x == rt_y:
        return False
    else:
        if par[rt_x] > par[rt_y]:
            rt_x, rt_y = rt_y, rt_x
            w = -w
        par[rt_x] += par[rt_y]
        par[rt_y] = rt_x
        diff_weight[rt_y] = w
        return True


def find(x):
    if par[x] < 0:
        return x
    else:
        diff_weight[x] += diff_weight[par[x]]
        par[x] = find(par[x])
        return par[x]


def weight(x):
    find(x)
    return diff_weight[x]


def is_same(x, y):
    return find(x) == find(y)


def diff(x, y):
    return weight(y)-weight(x)


if __name__ == '__main__':
    n, m = map(int, input().split())
    par = [-1]*(n+1)
    diff_weight = [0]*(n+1)
    query = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        query.append((l, r, d))
    print(solve(n, query))

Submission status: Wrong Answer

Solution code:
def solve(n, query):
    for l, r, d in query:
        if is_same(l, r):
            if d != diff(l, r):
                return 'No'
        else:
            unite(l, r, d)
    return 'Yes'


def unite(x, y, w):
    w += weight(x) - weight(y)
    rt_x = find(x)
    rt_y = find(y)
    if rt_x == rt_y:
        return
    if rank[rt_x] >= rank[rt_y]:
        par[rt_y] = rt_x
        diff_weight[rt_y] = w
        if rank[rt_x] == rank[rt_y]:
            rank[rt_x] += 1
    else:
        par[rt_x] = rt_y
        diff_weight[rt_x] = -w


def find(x):
    if par[x] < 0:
        return x
    else:
        diff_weight[x] += diff_weight[par[x]]
        par[x] = find(par[x])
        return par[x]


def weight(x):
    find(x)
    return diff_weight[x]


def is_same(x, y):
    return find(x) == find(y)


def diff(x, y):
    return weight(y)-weight(x)


if __name__ == '__main__':
    n, m = map(int, input().split())
    par, rank = [-1]*(n+1), [0]*(n+1)
    diff_weight = [0]*(n+1)
    query = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        query.append((l, r, d))
    print(solve(n, query))

Submission status: Wrong Answer

Solution code:
def solve(n, b, query):
    for l, r, d in query:
        if is_same(l, r):
            if diff(l, r) != d:
                return 'No'
        else:
            unite(l, r, d)
    return 'Yes'


def weight(x):
    find(x)
    return diff_weight[x]


def diff(x, y):
    return weight(y)-weight(x)


def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        diff_weight[x] += diff_weight[par[x]]
        return par[x]


def is_same(x, y):
    return find(x) == find(y)


def unite(x, y, w):
    root_of_x = find(x)
    root_of_y = find(y)
    w += weight(x)
    w -= weight(y)
    if root_of_x == root_of_y:
        return False

    if rnk[root_of_x] < rnk[root_of_y]:
        par[root_of_x] = root_of_y
        w = -w
    else:
        par[root_of_y] = root_of_x
        diff_weight[root_of_y] = w
        if rnk[root_of_x] == rnk[root_of_y]:
            rnk[root_of_x] += 1
    return True


if __name__ == '__main__':
    n, m = map(int, input().split())
    query = []
    par, rnk = [-1]*n, [0]*n
    diff_weight = [0]*n

    for i in range(m):
        l, r, d = map(int, input().split())
        l, r = l-1, r-1
        query.append((l, r, d))

    for i in range(n):
        par[i] = i

    print(solve(n, m, query))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]


n, m = map(int, input().split())
graph = defaultdict(list)
edges = []
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges.append((l, r, d))
    graph[l].append((d, r))
    graph[r].append((d, l))

dist = dijkstra(graph, n, 0)
possible = True
for l, r, d in edges:
    if d != abs(dist[l] - dist[r]):
        possible = False
        break

if possible:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
	N, M = map(int,input().split())
	if M == 0:
		print("Yes")
		return
	pos = [[] for _ in range(N)]
	ans_pos = [[0 for _ in range(N)] for _ in range(N)]
	neg = [[] for _ in range(N)]
	ans_neg = [[0 for _ in range(N)] for _ in range(N)]
	for i in range(M):
		l, r, d = map(int, input().split())
		l, r = l-1, r-1
		pos[l].append([r, d])
		neg[r].append([l, d])

	def solve(original, answer, n):
		visited = [False for _ in range(n)]
		for i in range(n):
			if not original[i]:
				continue
			visited[i] = True
			vs = original[i]
			while vs:
				cur = vs.pop(0)
				if visited[cur[0]]:
					continue
				visited[cur[0]] = True
				answer[i][cur[0]] = cur[1]
				nex = original[cur[0]]
				if not nex:
					continue
				for add in nex:
					if visited[add[0]]:
						continue
					vs.append([add[0], cur[1]+add[1]])
				vs.sort(key=lambda x: x[1])
			visited = [False for _ in range(n)]

	solve(pos, ans_pos, N)
	solve(neg, ans_neg, N)

	ans_exist = True
	for i in range(N):
		for j in range(N):
			if ans_pos[i][j] != ans_neg[j][i]:
				ans_exist = False
				break

	if ans_exist:
		print("Yes")
	else:
		print("No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def compare(p,q,l):
    l_temp1=0
    l_temp2=0
    flag=0
    while(True):
        if q==p:
            flag=1
            break
        temp=RDW[q][0]
        if temp==q:
            break
        else:
            l_temp1+=RDW[q][2]
            q=temp
    if flag==0:
        while(True):
            if p==q:
                flag=1
                break
            temp=RDW[p][0]
            if temp==p:
                break
            else:
                l_temp2+=RDW[p][2]
                p=temp
    if flag==0:
        if RDW[p][1]>=RDW[q][1]:
            RDW[p][1]=max(RDW[p][1],RDW[q][1]+1)
            RDW[q][0]=p
            RDW[q][2]=l+l_temp2
        else:
            RDW[p][0]=q
            RDW[p][2]=-l-l_temp1
    else:
        ll=l_temp1-l_temp2
        if l!=ll:
            ff[0]=1
            
for i in range(M):
    a,b,c=LRD[i]
    compare(a-1,b-1,c)
    if ff[0]==1:
        print("No")
        break
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
N,M = map(int,input().split())
e = [[] for i in range(N)]
t = 0
for i in range(M):
    r,l,d = map(int,input().split())
    e[r-1].append([l-1,d])
    e[l-1].append([r-1,-d])
    t = r-1

col = [ float("inf") for i in range(N) ]
def dfs(i,c):

    for node in e[i]:
        if col[node[0]] == float("inf"):
            col[node[0]] = c + node[1]
            dfs(node[0],c+node[1])
        elif col[node[0]] != c + node[1]:
            print("No")
            exit()

dfs(t,0)

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
N,M = map(int,input().split())
e = [[] for i in range(N)]
t = 0
for i in range(M):
    r,l,d = map(int,input().split())
    e[r-1].append([l-1,d])
    e[l-1].append([r-1,-d])
    t = r-1

col = [ -1 for i in range(N) ]
def dfs(i,c):

    for node in e[i]:
        if col[node[0]] == -1:
            col[node[0]] = c + node[1]
            dfs(node[0],c+node[1])
        elif col[node[0]] != c + node[1]:
            print("No")
            exit()

dfs(t,0)

print("Yes")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.level = [0 for i in range(n)]
        self.weight = [0 for i in range(n)]

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

    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if self.level[px] < self.level[py]:
            self.par[px] = py
            self.weight[px] = -self.weight[x] + self.weight[y] + w
        else:
            self.par[py] = px
            self.weight[py] = + self.weight[x] - self.weight[y] - w
            if self.level[px] == self.level[py]:
                self.level[px] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

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

def solve(N, M):
    wuf = WeightedUnionFind(N+1)
    for i in range(M):
        L, R, D = map(int, input().split())
        if wuf.same(L, R):
            if wuf.diff(L, R) != D:
                return False
        else:
            wuf.union(L, R, D)
    return True

N, M = map(int, input().split())
if solve(N, M):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.level = [0] * n
        self.weight = [0] * n

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

    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if self.level[px] < self.level[py]:
            self.par[px] = py
            self.weight[px] = -self.weight[x] + self.weight[y] + w
        else:
            self.par[py] = px
            self.weight[py] = + self.weight[x] - self.weight[y] - w
            if self.level[px] == self.level[py]:
                self.level[px] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

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

def solve(N, M):
    wuf = WeightedUnionFind(N+1)
    for i in range(M):
        L, R, D = map(int, input().split())
        if wuf.same(L, R):
            if wuf.diff(L, R) != D:
                return False
        else:
            wuf.union(L, R, D)
    return True

N, M = map(int, input().split())
if solve(N, M):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+1)

def dfs(v):
    for u, d in es[v]:
        if x[u] == None:
            x[u] = x[v] + d
            dfs(u)
        elif x[u] != x[v] + d:
            return False
    return True

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    L, R, D = map(int, input().split())
    es[L].append((R, D))
    es[R].append((L, -D))
x = [None for i in range(N+1)]
flag = True
for v in range(1, N+1):
    if x[v] == None:
        x[v] = 0
        if dfs(v) == False:
            flag = False
            break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
w=[[200001]*(n+1) for i in range(n+1)]
t=[]
for i in range(m):
    l,r,d=[int(i) for i in input().split()]
    w[l][r]=d
    w[r][l]=d
    t.append((l,r,d))
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            w[j][k]=min(w[j][k],w[j][i]+w[i][k])

f=1
for i in t:
    if w[i[0]][i[1]]<i[2]:
        f=0
print(["No","Yes"][f])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5+5)
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))
INF=10**9
x_list=[INF]*n
def dfs(x):
    for i in graph[x]:
        if x_list[i[0]]==INF:
            x_list[i[0]]=x_list[x]+i[1]
            dfs(i[0])
        else:
            if x_list[i[0]]==x_list[x]+i[1]:
                pass
            else:
                print('No')
                sys.exit()
for i in range(n):
    if x_list[i]==INF:
        x_list[i]=0
        dfs(i)
print('Yes')

Submission status: Wrong Answer

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

dic={}
id=1
ans=True

if m > 0:
  l,r,d = (int(i) for i in input().split())
  dic[id]={}
  dic[id][l]=0
  dic[id][r]=d

if m > 1:
  for j in range(m-1):
    l,r,d = (int(i) for i in input().split())
    for i in dic.values():
        if l in i.keys():
            if r in i.keys():
                tmp1=dic[id][l]+d
                if tmp1 == dic[id][r]:
                    pass
                else:
                    ans=False
                    break
            else:
                tmp=dic[id][l]
                dic[id][r]=tmp+d
        else:
            if r in i.keys():
                dic[id][l]=dic[id][r]-d
            else:
                dic[id][l]=0
                dic[id][r]=d
    
print('Yes' if ans==True else 'No')

Submission status: Wrong Answer

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

dic={}
id=1
ans=True

if m > 0:
  l,r,d = (int(i) for i in input().split())
  dic[id]={}
  dic[id][l]=0
  dic[id][r]=d

if m > 1:
  for j in range(m-1):
    l,r,d = (int(i) for i in input().split())
    for i in dic.values():
        if l in i.keys():
            if r in i.keys():
                tmp1=dic[id][l]+d
                if tmp1 == dic[id][r]:
                    pass
                else:
                    ans=False
                    break
            else:
                tmp=dic[id][l]
                dic[id][r]=tmp+d
        else:
            dic[id][l]=0
            dic[id][r]=d
    
print('Yes' if ans==True else 'No')

Submission status: Wrong Answer

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

dic={}
id=1
ans=True

if m > 0:
  l,r,d = (int(i) for i in input().split())
  dic[id]={}
  dic[id][l]=0
  dic[id][r]=d

if m > 1:
  for j in range(m-1):
    l,r,d = (int(i) for i in input().split())
    for i in dic.values():
        if l in i.keys():
            if r in i.keys():
                tmp1=dic[id][l]+d
                if tmp1 == dic[id][r]:
                    pass
                else:
                    ans=False
                    break
            else:
                tmp=dic[id][l]
                dic[id][r]=tmp+d
        else:
            pass
    
print('Yes' if ans==True else 'No')

Submission status: Wrong Answer

Solution code:
n,m=(int(i) for i in input().split())
ans= True
dic={}
a=100000

if m > 0:
  l,r,d = (int(i) for i in input().split())
  dic[l]=0
  dic[r]=d

if m > 1:
  for j in range(m-1):
    l,r,d = (int(i) for i in input().split())
    if l in dic.keys():
      tmp=dic[l]
      if r in dic.keys():
        tmp1=dic[r]
        if tmp1-tmp == d:
            pass
        else:
            ans= False
      else:    
        dic[r]=tmp+d
    else:
      if r in dic.keys():
        tmp=dic[r]
        dic[l]=tmp-d
      else:
        dic[l]=0+a
        dic[r]=d+a
        a+=a
        
print('Yes' if ans==True else 'No')

Submission status: Wrong Answer

Solution code:
n,m=(int(i) for i in input().split())
ans= True
dic={}

if m > 0:
  l,r,d = (int(i) for i in input().split())
  dic[l]=0
  dic[r]=d

if m > 1:
  for j in range(m-1):
    l,r,d = (int(i) for i in input().split())
    if l in dic.keys():
      tmp=dic[l]
      if r in dic.keys():
        tmp1=dic[r]
        if tmp1-tmp == d:
            pass
        else:
            ans= False
      else:    
        dic[r]=tmp+d
    else:
      if r in dic.keys():
        tmp=dic[r]
        dic[l]=tmp-d
      else:
        dic[l]=0
        dic[r]=d
        
print('Yes' if ans==True else 'No')

Submission status: Wrong Answer

Solution code:
n,m=(int(i) for i in input().split())
ans= True
dic={}

if m > 0:
  l,r,d = (int(i) for i in input().split())
  dic[l]=0
  dic[r]=d

if m > 1:
  for j in range(1,m):
    l,r,d = (int(i) for i in input().split())
    if l in dic.keys():
      tmp=dic[l]
      if r in dic.keys():
        tmp1=dic[r]
        if tmp1-tmp == d:
            pass
        else:
            ans= False
      else:    
        dic[r]=tmp+d
    else:
      if r in dic.keys():
        tmp=dic[r]
        dic[l]=tmp-d
      else:
        dic[l]=0
        dic[r]=d
        
print('Yes' if ans==True else 'No')

Submission status: Wrong Answer

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

#a=100000
ans= True
dic={}

if m > 0:
  l,r,d = (int(i) for i in input().split())
#print(l,r,d)  
  dic[l]=0
  dic[r]=d
#print(dic)

if m > 1:
  for j in range(1,m):
    l,r,d = (int(i) for i in input().split())
#print(l,r,d)
    if l in dic.keys():
      tmp=dic[l]
      if r in dic.keys():
        tmp1=dic[r]
        if tmp1-tmp == d:
            pass
        else:
            ans= False
      else:    
        dic[r]=tmp+d
    else:
      dic[l]=0
      if r in dic.keys():
        tmp=dic[r]
        dic[l]=tmp-d
      else:
        dic[r]=d
        
print('Yes' if ans==True else 'No')

Submission status: Wrong Answer

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]
        if r_pos > l_pos+d:
            for j in c[g[l][0]]:
                j[1] += r_pos - d - l_pos
                if j[1] > 10**9:
                    flag = False
                    break
            for j in c[g[r][0]]:
                g[j[0]][1] += g[c[g[l][0]][-1][0]][1] + 1
            c[g[r][0]].extend(c[g[l][0]])
            for j in c[g[l][0]]:
                g[j[0]][0] = g[r][0]

        else:
            for j in c[g[r][0]]:
                j[1] += l_pos + d - r_pos
                if j[1] > 10**9:
                    flag = False
                    break
            for j in c[g[l][0]]:
                g[j[0]][1] += g[c[g[r][0]][-1][0]][1] + 1
            c[g[l][0]].extend(c[g[r][0]])
            for j in c[g[r][0]]:
                g[j[0]][0] = g[l][0]

    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = g[c[g[l][0]][-2][0]][1]+1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = g[c[g[r][0]][-2][0]][1]+1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
    if not flag:
        break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]
        if r_pos > l_pos+d:
            for j in c[g[l][0]]:
                j[1] += r_pos - d - l_pos
            for j in c[g[r][0]]:
                g[j[0]][1] += g[c[g[l][0]][-1][0]][1] + 1
            c[g[r][0]].extend(c[g[l][0]])
            for j in c[g[l][0]]:
                g[j[0]][0] = g[r][0]

        else:
            for j in c[g[r][0]]:
                j[1] += l_pos + d - r_pos
            for j in c[g[l][0]]:
                g[j[0]][1] += g[c[g[r][0]][-1][0]][1] + 1
            c[g[l][0]].extend(c[g[r][0]])
            for j in c[g[r][0]]:
                g[j[0]][0] = g[l][0]

    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = g[c[g[l][0]][-2][0]][1]+1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = g[c[g[r][0]][-2][0]][1]+1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


class PotentialUnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.diffweight = [0 for i in range(N)]

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            self.diffweight[x] += self.diffweight[self.table[x]]
            return self.table[x]

    def Unite(self,x,y,w): #xとyをDiff(x,y)=W で繋げる
        w = w - self.Weight(y) + self.Weight(x)
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
            self.diffweight[y] = w
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            self.diffweight[x] = -w
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def Weight(self,x): # 重さ(根からの距離)
        self.Find(x)
        return self.diffweight[x]

    def Diff(self,x,y): # 繋がってる二点間距離
        return self.Weight(y) - self.Weight(x)


N,M = inpl()
PUF = PotentialUnionFind(N)

for _ in range(M):
    l,r,d = inpl()
    l,r = l-1,r-1
    if PUF.Check(l,r):
        if PUF.Diff(l,r) == d:
            continue
        else:
            print('No')
            exit()
    else:
        PUF.Unite(l,r,d)

print('Yes')