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:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def calc(A, B, C, now_t):
    ans = A * now_t + B * math.sin(C * now_t * math.pi)
    return ans


def main():
    num, hint_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(hint_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)
    for i in range(hint_num):
        l, r , d = data[i]
        graph_data[l].add(r)
        graph_data[r].add(l)
        dist_data[(l, r)] = d
        dist_data[(r, l)] = -1 * d

    position = [-1 for i in range(num + 1)]
    # position[1] = 0

    # now_set = set()
    # next_set = set()
    # now_set.add(1)

    flg = 1
    for i in range(1, num + 1):
        if position[i] == -1:
            position[i] = 0
        now_set = set()
        next_set = set()
        now_set.add(i)
        while len(now_set) > 0:
            for now_ele in now_set:
                for next_ele in graph_data[now_ele]:
                    length = dist_data[(now_ele, next_ele)]
                    if position[next_ele] == -1:
                        position[next_ele] = position[now_ele] + length
                        next_set.add(next_ele)
                    else:
                        if position[next_ele] != position[now_ele] + length:
                            flg = 0
                            break
            now_set = next_set
            next_set = set()

    max_data = -10 ** 10
    min_data = 10 ** 10
    for i in range(1, num + 1):
        if position[i] == -1:
            continue
        max_data = max(max_data, position[i])
        min_data = min(min_data, position[i])

    if max_data - min_data > 10 ** 9:
        flg = 0

    # print(position)

    if flg:
        print('Yes')
    else:
        print('No')





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict, deque

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    visited = [False] * N
    pos = [None] * N
    adj = [set() for _ in range(N)]

    for l, r, d in zip(L, R, D):
        adj[l].add((r, d))
        adj[r].add((l, -d))
    
    for i, vis in enumerate(visited):
        if vis:
            continue
        pos[i] = 0
        Q = deque([i], N)
        while len(Q) > 0:
            u = Q.popleft()
            visited[u] = True
            for v, d in adj[u]:
                if pos[v] is None:
                    pos[v] = pos[u] + d
                elif pos[v] != pos[u] + d:
                    print(NO)
                    return

                if visited[v]:
                    continue
                Q.append(v)
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens)) - 1
        R[i] = int(next(tokens)) - 1
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict, deque

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    visited = [False] * N
    pos = [None] * N
    adj = [set()] * N

    for l, r, d in zip(L, R, D):
        adj[l].add((r, d))
        adj[r].add((l, -d))
    
    for i, vis in enumerate(visited):
        if vis:
            continue
        pos[i] = 0
        Q = deque([i], N)
        while len(Q) > 0:
            u = Q.popleft()
            visited[u] = True
            for v, d in adj[u]:
                if pos[v] is None:
                    pos[v] = pos[u] + d
                elif pos[v] != pos[u] + d:
                    print(NO)
                    return

                if visited[v]:
                    continue
                Q.append(v)
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens)) - 1
        R[i] = int(next(tokens)) - 1
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input=sys.stdin.readline
N,M=map(int,input().split())

C=[0 for i in range(N+1)]
L=[[]for i in range(N+1)]
A=[10**12 for i in range(N+1)]
B=[]

for i in range(M):
    l,r,d=map(int,input().split())
    B.append([l,r,d])
    C[r]=1
    L[l].append([l,r,d])
for i in range(N+1):
    if C[i]==0:
        A[i]=0
for i in range(1,N+1):
    if A[i]==0:
        if len(L[i])>0:
            Q=[]
            for l,r,d in L[i]:
                Q.append([A[i]+d,r,l])
            #print(Q)
            heapq.heapify(Q)
            for j in range(10**6):
                if len(Q)==0:
                    break
                else:
                    q=Q[0]
                    if A[q[1]]>=q[0]:
                        A[q[1]]=q[0]
                        for k in L[q[1]]:
                            heapq.heappush(Q,[q[0]+k[2],k[1],k[0]])
                heapq.heappop(Q)
#print(C)
#print(A)
for i in range(M):

    if A[B[i][1]]!=A[B[i][0]]+B[i][2]:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import heapq

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

C=[0 for i in range(N+1)]
L=[[]for i in range(N+1)]
A=[0 for i in range(N+1)]
B=[]

for i in range(M):
    l,r,d=map(int,input().split())
    B.append([l,r,d])
    C[r]=1
    L[l].append([l,r,d])
for i in range(N+1):
    if C[i]==0:
        A[i]=0
for i in range(1,N+1):
    if A[i]==0:
        if len(L[i])>0:
            Q=[]
            for l,r,d in L[i]:
                Q.append([A[i]+d,r,l])
            #print(Q)
            heapq.heapify(Q)
            for j in range(10**6):
                if len(Q)==0:
                    break
                else:
                    q=Q[0]
                    if A[q[1]]>=q[0]:
                        A[q[1]]=q[0]
                        for k in L[q[1]]:
                            heapq.heappush(Q,[q[0]+k[2],k[1],k[0]])
                heapq.heappop(Q)
#print(C)
#print(A)
for i in range(M):

    if A[B[i][1]]!=A[B[i][0]]+B[i][2]:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import heapq

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

C=[0 for i in range(N+1)]
L=[[]for i in range(N+1)]
A=[10**15 for i in range(N+1)]
B=[]

for i in range(M):
    l,r,d=map(int,input().split())
    B.append([l,r,d])
    C[r]=1
    L[l].append([l,r,d])
for i in range(N+1):
    if C[i]==0:
        A[i]=0
for i in range(1,N+1):
    if A[i]==0:
        if len(L[i])>0:
            Q=[]
            for l,r,d in L[i]:
                Q.append([A[i]+d,r,l])
            #print(Q)
            heapq.heapify(Q)
            for j in range(10**6):
                if len(Q)==0:
                    break
                else:
                    q=Q[0]
                    if A[q[1]]>=q[0]:
                        A[q[1]]=q[0]
                        for k in L[q[1]]:
                            heapq.heappush(Q,[q[0]+k[2],k[1],k[0]])
                heapq.heappop(Q)
#print(C)
#print(A)
for i in range(M):

    if A[B[i][1]]!=A[B[i][0]]+B[i][2]:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())

C=[0 for i in range(N+1)]
L=[[]for i in range(N+1)]
A=[]
for i in range(M):
    l,r,d=map(int,input().split())
    A.append([r,l,d])
A.sort()    

for i in range(M):
    C[A[i][0]]=C[A[i][1]]+A[i][2]
    
for i in range(M):
    if C[A[i][0]]!=C[A[i][1]]+A[i][2]:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

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

class WeightedUnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y
        
    def unite(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        
        if px == py:
            return True
        
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        elif self.rank[px] < self.rank[py]:
            px, py = py, px
            w *= -1

        self.par[py] = px
        self.weight[py] = self.weight[x] - self.weight[y] - w
                
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

t = WeightedUnionFind(N + 1)
for l, r, d in X:
    if t.same(l, r):
        if t.diff(l, r) != d:
            print('No')
            break
    else:
        t.unite(l, r, d)
else:
    print('Yes')

Submission status: Wrong Answer

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

A = [[] for i in range(N)]

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,-d])
    
ans = "Yes"

distance = ["#" for i in range(N)]

flg = 0

for i in range(N) :
    if flg :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        now = stack.pop()
        
        for to,d in A[now] :
            if distance[to] == "#" :
                distance[to] = distance[now] + d
                stack.append(to)
            
            elif distance[to] == distance[now] + d :
                ans = "No"
                stack = []
                flg = 1
                break
            
print(ans)

Submission status: Wrong Answer

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

A = [[] for i in range(N)]

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,-d])
    
ans = "Yes"

distance = ["#" for i in range(N)]

flg = 0

for i in range(N) :
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        now = stack.pop()
        
        for to,d in A[now] :
            if distance[to] == "#" :
                distance[to] = distance[now] + d
                stack.append(to)
            
            elif distance[to] == distance[now] + d :
                ans = "No"
                stack = []
                flg = 1
                break
            
print(ans)

Submission status: Wrong Answer

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

for i in range(M) :
    l,r,d = map(int,input().split())
    
    l -= 1
    r -= 1
    
    A[l].append([r,d])
    A[r].append([l,d])

distance = ["#" for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg == 1 :
        break
    
    if distance[i] != "#" :
        continue
    
    distance[i] = 0
    stack = [i]
    
    while stack :
        v = stack.pop()
        
        for to,d in A[v] :
            if distance[to] == "#" :
                distance[to] = distance[v] + d
                stack.append(to)
            
            elif distance[to] != distance[v] + d :
                ans = "No"
                stack = []
                flg = 1
                break
                

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = ["#" for i in range(N+1)]
X = []
ans = "Yes"

for i in range(M) :
    l,r,d = map(int,input().split())
    
    if l > r :
        l,r = r,l
        d *= -1
    X.append([l,r,d])

X = sorted(X, key=lambda x: x[0])

for i in range(len(X)) :
    l,r,d = X[i]
    if i == 0 :
        A[l] = 0
        A[r] = d
    
    elif A[l] == "#" :
        continue
    
    elif A[r] == "#" :
        if A[l] == "#" :
            continue
        
        A[r] = A[l] + d
    
    else :
        if A[r] != A[l] + d :
            ans = "No"
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = ["#" for i in range(N+1)]

ans = "Yes"

for i in range(M) :
    l,r,d = map(int,input().split())
    
    if l > r :
        l,r = r,l
        d *= -1
    
    if i == 0 :
        A[l] = 0
        A[r] = d
    
    elif A[l] == "#" :
        continue
    
    elif A[r] == "#" :
        if A[l] == "#" :
            continue
        
        A[r] = A[l] + d
    
    else :
        if A[r] != A[l] + d :
            ans = "No"
            break

print(ans)

Submission status: Wrong Answer

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

ans = "Yes"

for i in range(M) :
    l,r,d = map(int,input().split())
    
    if l > r :
        l,r = r,l
        d *= -1
    
    if i == 0 :
        A[l].append(0)
        A[r].append(d)
    
    elif len(A[l]) == 0 :
        continue
    
    elif len(A[r]) == 0 :
        A[r].append(A[l][0]+d)
    
    elif len(A[r]) >= 1 :
        if A[r][0] != A[l][0] + d :
            ans = "No"
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M=map(int,input().split())
P=[list(map(int,input().split())) for i in range(M)]
inf=10**15
c=[[] for i in range(N)]
for i,j,w in P:
    c[i-1].append((j-1,w))
    c[j-1].append((i-1,-w))
d=[inf]*N
v=[0]*N
a=0
import sys
sys.setrecursionlimit(10**7)
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=d[p]+w
            v[n]=1
            dfs(n,v,d)
        elif d[p]+w!=d[n]:
            return -1
    return 0
s=0
while True:
    d[s]=0
    v[s]=1
    a=dfs(s,v,d)
    if a<0:
        break
    try:
        s=d.index(inf,s)
    except ValueError:
        break
print(['Yes','No'][a])

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M=map(int,input().split())
P=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[] for i in range(N)]
for i,j,w in P:
    c[i-1].append((j-1,w))
    c[j-1].append((i-1,-w))
inf=10**10
d=[inf]*N
v=[0]*N
a=0
import sys
sys.setrecursionlimit(10**7)
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=d[p]+w
            v[n]=1
            dfs(n,v,d)
        elif d[p]+w!=d[n]:
            return -1
    return 0
s=0
while True:
    d[s]=0
    v[s]=1
    a=dfs(s,v,d)
    if a<0:
        break
    try:
        s=d.index(inf,s)
    except ValueError:
        break
print(['Yes','No'][a])

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M=map(int,input().split())
P=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[] for i in range(N)]
for i,j,w in P:
    c[i-1].append((j-1,w))
    c[j-1].append((i-1,-w))
inf=10**10
d=[inf]*N
v=[0]*N
a=0
import sys
sys.setrecursionlimit(10**7)
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=min(d[n],d[p]+w)
            v[n]=1
            dfs(n,v,d)
        elif d[p]+w!=d[n]:
            return -1
    return 0
s=0
while True:
    d[s]=0
    v[s]=1
    a=dfs(s,v,d)
    if a<0:
        break
    try:
        s=d.index(inf,s)
    except ValueError:
        break
print(['Yes','No'][a])

Submission status: Wrong Answer

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

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

P=[i for i in range(N+1)]
r=[0 for i in range(N+1)]

def find(a):
    if a==P[a]:
        pass
    else:
        return find(P[a])
        
def union(a,b,c):
    P[b]=P[a]
    r[b]=c
    
def find2(a,b):
    if a==P[a]:
        return b+r[a]
    else:
        return find2(P[a],b+r[a])
L=[]
for i in range(M):
    a,b,c=map(int,input().split())
    union(a,b,c)
    L.append([a,b,c])
    
for i in range(1,N+1):
    r[i]=find2(i,0)
    
#print(L)

for i in L:
    if r[i[0]]!=r[i[1]]-i[2]:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
# 重み付きUnion-Findデータ構造
class WeightedUnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
        self.weights = [0] * numV

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

    def union(self, x, y, wt):
        wtX = self.getWeight(x)
        wtY = self.getWeight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return wtY == wtX+wt
        wt += wtX - wtY
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
            self.weights[x] = -wt
        else:
            self.pars[y] = x
            self.weights[y] = wt
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        return True

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

    def getWeight(self, x):
        self.find(x)
        return self.weights[x]

    def getDiff(self, x, y):
        if self.find(x) == self.find(y):
            return self.getWeight(y) - self.getWeight(x)
        else:
            return float('inf')


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

WUF = WeightedUnionFind(N)
ans = 'Yes'
for _ in range(M):
    L, R, D = map(int, input().split())
    if not WUF.union(L-1, R-1, D):
        ans = 'No'

print(ans)

Submission status: Wrong Answer

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

N,M=map(int,input().split())
P=[i for i in range(N+1)]
L=[0 for i in range(N+1)]
Q=[]
def find(a):
    if P[a]==a:
        return a
    else:
        return find(P[a])

def union(b,c,d):
    B=find(b)
    C=find(c)
    P[C]=P[B]
    L[c]=L[b]+d

for i in range(M):
    l,r,d=map(int,input().split())
    Q.append([l,r,d])
    union(l,r,d)
#print(P)
#print(L)

for i in Q:
    if L[i[1]]-L[i[0]]==i[2]:
        continue
    else:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
P=[i for i in range(N+1)]
L=[0 for i in range(N+1)]
Q=[]
def find(a):
    if P[a]==a:
        return a
    else:
        return find(P[a])

def union(b,c,d):
    B=find(b)
    C=find(c)
    P[C]=P[B]
    L[c]=L[b]+d

for i in range(M):
    l,r,d=map(int,input().split())
    Q.append([l,r,d])
    union(l,r,d)
#print(P)
#print(L)

for i in Q:
    if L[i[1]]-L[i[0]]==i[2]:
        continue
    else:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
mem=[0]*(n+1)
job=[]
flag=True
for i in range(m):
  a,b,d=map(int,input().split())
  if a<=b:
  	job.append([a,b,d])
  else:
  	job.append([b,a,-d])
job=sorted(job, key=lambda x:x[0])
for i in range(m):
  a=job[i][0]
  b=job[i][1]
  d=job[i][2]
  tmp=arr[b]-arr[a]
  if mem[a]*mem[b]==0:
  	if mem[b]==0:
  		arr[b]=arr[a]+d
  	else:
  		arr[a]=arr[b]-d
  	mem[a]=1
  	mem[b]=1
  else:
    if tmp!=d:
      flag=False
      break
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
mem=[0]*(n+1)
job=[]
flag=True
for i in range(m):
  a,b,d=map(int,input().split())
  if a<=b:
  	job.append([a,b,d])
  else:
  	job.append([b,a,-d])
job=sorted(job, key=lambda x:x[0])
print(job)
for i in range(m):
  a=job[i][0]
  b=job[i][1]
  d=job[i][2]
  tmp=arr[b]-arr[a]
  if mem[a]*mem[b]==0:
  	if mem[b]==0:
  		arr[b]=arr[a]+d
  	else:
  		arr[a]=arr[b]-d
  	mem[a]=1
  	mem[b]=1
  else:
    if tmp!=d:
      flag=False
      break
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
mem=[0]*(n+1)
flag=True
for _ in range(m):
  a,b,d=map(int,input().split())
  tmp=arr[b]-arr[a]
  if mem[a]*mem[b]==0:
    mem[a]=1
    mem[b]=1
    arr[b]=arr[a]+d
  else:
    if tmp!=d:
      flag=False
      break
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
flag=True
for _ in range(m):
  a,b,d=map(int,input().split())
  tmp=arr[a]+d
  if arr[b]!=0 and arr[b]!=tmp:
    flag=False
  arr[b]=tmp
if flag:
  for i in range(n):
    if arr[i]!=0 and arr[i+1]!=0:
      if arr[i] > arr[i+1]:
        flag=False
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
flag=True
for _ in range(m):
  a,b,d=map(int,input().split())
  tmp=arr[a]+d
  if arr[b]!=0 and arr[b]!=tmp:
    flag=False
  arr[b]=tmp
  print(arr)
if flag:
  for i in range(n):
    if arr[i]!=0 and arr[i+1]!=0:
      if arr[i] > arr[i+1]:
        flag=False
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
flag=True
for _ in range(m):
  a,b,d=map(int,input().split())
  tmp=arr[a]+d
  if arr[b]!=0 and arr[b]!=tmp:
    flag=False
  arr[b]=tmp
if flag:
  for i in range(n):
    if arr[i] > arr[i+1]:
      flag=False
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[0]*(n+1)
flag=True
for _ in range(m):
  a,b,d=map(int,input().split())
  if b>a:
    tmp=arr[a]+d
    if arr[b]!=0 and arr[b]!=tmp:
      flag=False
    arr[b]=tmp
  else:
    tmp=arr[b]-d
    if arr[a]!=0 and arr[a]!=tmp:
      flag=False
    arr[a]=tmp
if flag:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
if M == 0:
    print("Yes")
    exit()
LRD = list(list(map(int,input().split())) for i in range(M))
#print(LRD)
d = {LRD[0][0]:0}

for i in range(M):
    if (LRD[i][0] in d) and (LRD[i][1] not in d):
          d[LRD[i][1]] = d[LRD[i][0]]+LRD[i][2]
    elif (LRD[i][0] in d) and (LRD[i][1] in d):
        if d[LRD[i][1]] != d[LRD[i][0]]+LRD[i][2]:
            print("No")
            exit()
        else:
            continue
    elif (LRD[i][0] not in d) and (LRD[i][1] in d):
        if d[LRD[i][1]] - LRD[i][2] < 0:
            print("No")
            exit()
        else:
            d[LRD[i][0]] = d[LRD[i][1]] - LRD[i][2]
    else:
        d[LRD[i][0]] = 0
        d[LRD[i][1]] = d[LRD[i][0]] + LRD[i][2]

print("Yes")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


N, M = map(int, input().split())
Un = WeightedUnionFind(N+1)

ans = "Yes"
for _ in range(M):
    l, r, w = map(int, input().split())
    if Un.same(l, r):
        if Un.diff(l, r) != w:
            ans = "NO"
            break
    else:
        Un.union(l, r, w)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
#lef[i]:iの左親,ran[i]:iの左親までの距離
lef = list(range(n+1))
ran = [0]*(n+1)

#左親の発見および更新
def f(x):
    if lef[x]==x:
        return x
    ran[x] = ran[x]+ran[lef[x]]
    lef[x]= f(lef[x])
    
    return lef[x]

for i in range(m):
    l,r,d = map(int,input().split())
    a = f(l)
    b = f(r)
    if a == b and ran[r]-ran[l] != d:
        print("No")
        exit()
    else:
        lef[b] = a
        ran[b] = ran[l]+d-ran[r]

print("Yes")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
#lef[i]:iの左親,ran[i]:iの左親までの距離
lef = list(range(n+1))
ran = [0]*(n+1)

#左親の発見および更新
def f(x):
    if lef[x]==x:
        return x
    lef[x] = f(lef[x])
    ran[x] = ran[x]+ran[lef[x]]
    return lef[x]

for i in range(m):
    l,r,d = map(int,input().split())
    a = f(l)
    b = f(r)
    if a == b and ran[r]-ran[l] != d:
        print("No")
        exit()
    else:
        lef[b] = a
        ran[b] = ran[l]+d-ran[r]

print("Yes")

Submission status: Wrong Answer

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

Node = [Inf for i in range(N)]
for i in range(N):
    if Node[i] == Inf:
        Node[i] = 0
        Q = [i]
        while Q:
            now = Q.pop(0)
            for e in Edge[now]:
                if Node[e[0]] == Inf:
                    Node[e[0]] = Node[now] + e[1]
                    Q.append(e[0])
                elif Node[now] + e[1] != Node[e[0]]:
                    print("No")
                    break
        else:
            continue
    else:
        continue
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
def find(x):
    if par[x] == x:
        return x
    else:
        dist[x] += dist[par[x]]
        par[x] = find(par[x])
        return par[x]
N, M = inpl()
par = list(range(N+1))
dist = [0 for _ in range(N+1)]

for _ in range(M):
    l, r, d = inpl()
    fl = find(l)
    fr = find(r)
    if fl != fr:
        par[fr] = fl
        dist[fr] = d + dist[l] - dist[r]
    elif d + dist[l] - dist[r] != 0:
        print('No')
        break
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
def find(x):
    if par[x] == x:
        return x
    else:
        dist[x] += dist[par[x]]
        return find(par[x])
N, M = inpl()
par = list(range(N+1))
dist = [0 for _ in range(N+1)]

for _ in range(M):
    l, r, d = inpl()
    fl = find(l)
    fr = find(r)
    if fl != fr:
        par[fr] = fl
        dist[fr] = d + dist[l] - dist[r]
    elif d + dist[l] - dist[r] != 0:
        print('No')
        break
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
def find(x):
    if par[x] == x:
        return x
    else:
        dist[x] += dist[par[x]]
        return find(par[x])
N, M = inpl()
par = list(range(N+1))
dist = [0 for _ in range(N+1)]

for _ in range(M):
    l, r, d = inpl()
    fl = find(l)
    fr = find(r)
    if fl != fr:
        par[r] = fl
        dist[fr] = d + dist[l] - dist[r]
    elif d + dist[l] - dist[r] != 0:
        print('No')
        break
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
        self.dist = [0 for _ in range(num)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
        elif self.dist[ry] != d + self.dist[x] - self.dist[y]:
            return False
        return True 
    

N, M = inpl()
X = UnionFind(N)
for _ in range(M):
    l, r, d = inpl()
    if r < l:
        r,l,d= l,r,-d
    if not X.union(l-1, r-1, d):
        print('No')
        break
    
else:
    print('Yes')