Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size + 1)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

def solve(N, M, lrd):
    uf = UnionFind(N + 1)
    for l, r, d in lrd:
        uf.union(l, r)
    xs = {}
    for i in range(1, N + 1):
        n = uf.find(i)
        if not n in xs: xs[n] = {}
        xs[n][i] = None
    for l, r, d in lrd:
        for row in xs.values():
            if l in row:
                break
        if row[l] is None:
            if row[r] is None:
                row[r] = 0
            row[l] = row[r] - d
        else:
            if row[r] is None:
                row[r] = row[l] + d
            else:
                if row[l] != row[r] - d:
                    return False
    for row in xs.values():
        vs = list(row.values())
        if vs[0] is None:
            continue
        if max(vs) - min(vs) > 10**9:
            return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if time.time() - start > 0.8:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
if M == 0:
	print('Yes')
	exit()
man = [None for i in range(N)]
info = []
for i in range(M):
	L,R,D  = map(int,input().split())
	info.append((L-1,R-1,D))
	info.append((R-1,L-1,-D))
 
 
info.sort()
man[info[0][0]] = 0
flag = True
for (l,r,d) in info:
	if man[l] == None:
		if man[r] != None:
			man[l] = man[r] - d
		elif l > r:
			man[l] = 0
		else:
			continue
	if man[r] != None:
		if man[l] + d != man[r]:
			flag = False
			break
	else:
		man[r] = man[l] + d
if flag:
	print('Yes')
else:
	print('No')

Submission status: Wrong Answer

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

x=[0 for _ in range(N)]
gp=[i for i in range(N)]

for _ in range(M):
    l,r,d=map(int,input().split())
    if(gp[l-1]==gp[r-1]):
        if(x[r-1]-x[l-1]!=d):
            print('No')
            break
    else:
        if(gp.count(gp[l-1])<gp.count(gp[r-1])):
            from_gp=gp[l-1]
            to_gp=gp[r-1]
        else:
            from_gp=gp[l-1]
            to_gp=gp[r-1]
        x=[x_+d+gp[l-1] if gp[i]==gp[r-1] else x_ for i,x_ in enumerate(x)]
        gp=[to_gp if gp_==from_gp else gp_ for gp_ in gp]
        if(max(x)>100000):
            print('No')
            break
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(300000)


def dfs(x, ls, rs, pos):
    xpos = 0 if pos[x] is None else pos[x]
    pos[x] = 0
    for r, d in ls.get(x, []):
        if pos[r] is not None:
            if pos[r] - xpos != d:
                return False
        else:
            pos[r] = xpos + d
            if not dfs(r, ls, rs, pos):
                return False
    for l, d in rs.get(x, []):
        if pos[l] is not None:
            if xpos - pos[l] != d:
                return False
        else:
            pos[l] = xpos - d
            if not dfs(l, ls, rs, pos):
                return False
    return True


def main():
    n, m = list(map(int, input().split()))
    pos = [None for _ in range(n + 1)]

    ls = {}
    rs = {}
    for _ in range(m):
        l, r, d = list(map(int, input().split()))
        lsl = ls.get(l, [])
        lsl.append((r, d))
        ls[l] = lsl
        rsr = rs.get(r, [])
        rsr.append((l, d))
        rs[r] = rsr

    for i in range(n):
        if not dfs(i+1, ls, rs, pos):
            print('No')
            return

    pos = list(filter(lambda x: x is not None, pos))
    if len(pos) > 0:
        L, R = min(pos), max(pos)
        if R - L > 1e9:
            print('No')
            return

    print('Yes')


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

people = [0] * (N+1)
peetru = [False] * (N+1)
for l, r, d in LRD:
    if (peetru[l]) & (peetru[r]):
        if abs(people[r]) + abs(people[l]) != d:
            print("No")
            break
    else:
        peetru[l] = True
        peetru[r] = True
        people[l] -= d
        people[r] += d
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
if M == 0:
	print('Yes')
	exit()
man = [None for i in range(N)]
info = []
for i in range(M):
	L,R,D  = map(int,input().split())
	info.append((L-1,R-1,D))
	info.append((R-1,L-1,-D))
 
 
info.sort()
man[info[0][0]] = 0
flag = True
for (l,r,d) in info:
	if man[l] == None:
		if man[r] != None:
			man[l] = man[r] - d
		else:
			continue
	if man[r] != None:
		if man[l] + d != man[r]:
			flag = False
			break
	else:
		man[r] = man[l] + d
 
for (l,r,d) in info:
	if man[l] == None:
		if man[r] != None:
			man[l] = man[r] - d
		else:
			man[l] = 0
	if man[r] != None:
		if man[l] + d != man[r]:
			flag = False
			break
	else:
		man[r] = man[l] + d
 
if flag:
	print('Yes')
else:
	print('No')

Submission status: Wrong Answer

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

conditions = sorted([[int(n) for n in input().split()] for _ in range(M)], reverse = True)

rights = [{} for _ in range(N)]
for l, r, d in conditions:
    if r-1 in rights[l-1] and rights[l-1][r-1] != d:
        print('No')
        sys.exit()
    if l-1 in rights[r-1] and rights[r-1][l-1] != -d:
        print('No')
        sys.exit()
    rights[l-1][r-1] = d
    for s, e in rights[r-1].items():
        if s in rights[l-1] and rights[l-1][s] != d + e:
            print('No')
            sys.exit()
        if l-1 in rights[s] and rights[s][l-1] != - (d + e):
            print('No')
            sys.exit()
        rights[l-1][s] = d + e

print('Yes')

Submission status: Wrong Answer

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()
	# dist = [[0 for _ in range(N)] for _ in range(N)]

	dist = defaultdict(lambda: 0)

	f = True
	for m in range(M):
		l,r,d = LI()
		l -= 1; r -= 1

		if r != 0:
			t = dist[(l,r-1)] + dist[(r-1, r)]

			if t != 0:
				if t != d:
					f = False
					break

			dist[(l,r)] = d
			dist[(r,l)] = d

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



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [set() for _ in range(n)]
    for l,r,d in a:
        e[l-1].add((r-1,d))
        e[r-1].add((l-1,-d))

    b = [False] * n
    def g(i,c):
        gt = time.time() - start
        if gt > 0.5:
            return True
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
loc = [float('inf')] * (N + 1)
ok = True
for _ in range(M):
    L, R, D = map(int, input().split())
    if loc[L] < float('inf'):
        if loc[R] < float('inf'):
            if loc[L] + D != loc[R]:
                ok = False
                break
        else:
            loc[R] = loc[L] + D
    else:
        if loc[R] < float('inf'):
            loc[L] = loc[R] - D
        else:
            loc[L], loc[R] = 0, D

lend, rend = float('inf'), -float('inf')
for x in loc:
    if x == float('inf'):
        pass
    else:
        if x < lend:
            lend = x
        if x > rend:
            rend = x
span = rend - lend if M > 0 else 0
ok = ok and (span <= 10 ** 9)
print('Yes' if ok else 'No')

Submission status: Wrong Answer

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

l, r, d = [], [], []

for i in range(m):
    l_, r_, d_ = map(int, input().split())
    if l_ < r_:
        l.append(l_-1)
        r.append(r_-1)
        d.append(d_)
    else:
        l.append(r_-1)
        r.append(l_-1)
        d.append(-d_)

import numpy as np
arg = np.argsort(l)

l, r, d = np.array(l)[arg], np.array(r)[arg], np.array(d)[arg]
p = np.array([np.nan for i in range(n)])

def solve():

    if m == 0:
        print("Yes")
        return

    for i in range(m):
        if np.isnan(p[l[i]]) and np.isnan(p[r[i]]):
            # initialize
            p[l[i]] = 0
            p[r[i]] = d[i]
        elif np.isnan(p[l[i]]):
            # add rule
            p[l[i]] = p[r[i]] - d[i]
        elif np.isnan(p[r[i]]):
            # add rule
            p[r[i]] = p[l[i]] + d[i]
        else:
            # check rule
            if p[r[i]] - p[l[i]] != d[i]:
                print("No")
                return


    # check max position
    # if np.max(p[~np.isnan(p)]) - np.min(p[~np.isnan(p)]) > 10**9:
    #     print("No")
    # else:
    if True:
        print("Yes")


solve()

Submission status: Wrong Answer

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

l, r, d = [], [], []

for i in range(m):
    l_, r_, d_ = map(int, input().split())
    if l_ < r_:
        l.append(l_-1)
        r.append(r_-1)
        d.append(d_)
    else:
        l.append(r_-1)
        r.append(l_-1)
        d.append(-d_)

import numpy as np
arg = np.argsort(l)

l, r, d = np.array(l)[arg], np.array(r)[arg], np.array(d)[arg]
p = np.array([np.nan for i in range(n)])

def solve():

    if m == 0:
        print("Yes")
        return

    for i in range(m):
        if np.isnan(p[l[i]]) and np.isnan(p[r[i]]):
            # initialize
            p[l[i]] = 0
            p[r[i]] = d[i]
        elif np.isnan(p[l[i]]):
            # add rule
            p[l[i]] = p[r[i]] - d[i]
        elif np.isnan(p[r[i]]):
            # add rule
            p[r[i]] = p[l[i]] + d[i]
        else:
            # check rule
            if p[r[i]] - p[l[i]] != d[i]:
                print("No")
                return


    # check max position
    if np.max(p[~np.isnan(p)]) - np.min(p[~np.isnan(p)]) > 10**9:
        print("No")
    else:
        print("Yes")


solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
union = list(range(N + 1))
dist = [0] * (N + 1)

def ascend(anc):
	tmp_d = dist[anc]
	if union[anc] == anc:
		return anc, tmp_d
	else:
		union[anc], d_sum = ascend(union[anc])
		dist[anc] = tmp_d + d_sum
	return union[anc], dist[anc]

def connect(l, r, d):
	l_anc, l_d = ascend(l)
	r_anc, r_d = ascend(r)
	if l_anc != r_anc:
		union[l_anc] = r_anc
		dist[l] = dist[r] + d

def is_union(l, r):
	l_anc, l_d = ascend(l)
	r_anc, r_d = ascend(r) 
	return l_anc == r_anc

def check(l, r, d):
	l_anc, l_d = ascend(l)
	r_anc, r_d = ascend(r)
	return r_d + d == l_d

for i in range(M):
	l, r, d = map(int, input().split())
	if is_union(l, r):
		if not check(l, r, d):
			print("No")
			break
	else:
		connect(l, r, d)
else:
	print("Yes")

Submission status: Wrong Answer

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

people = [0] * (N+1)
for l, r, d in LRD:
    if (people[l]!=0) & (people[r]!=0):
        if abs(people[r]) + abs(people[l]) != d:
            print("No")
            break
    else:
        people[l] -= d
        people[r] += d
else:
    print("Yes")

Submission status: Wrong Answer

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

# union-find改良
parent = list(range(N+1))
rank = [0] * (N+1)
pardist = [0] * (N+1) # ルートとの距離

def getRoot(x):
  if parent[x] == x:
    return x, 0
  else:
    # ルートに繋ぎ変える
    parent[x], dist = getRoot(parent[x])
    # ルートとの距離に更新
    pardist[x] += dist
    return parent[x], pardist[x]

# dist > 0
def unite(left, right, dist):
  lRoot, lPardist = getRoot(left)
  rRoot, rPardist = getRoot(right)
  if lRoot == rRoot:
    # 矛盾がないかチェック
    if rPardist - lPardist != dist:
      print('No')
      exit()
  else:
    # 矛盾は起きない
    # ルート間の距離だけ更新して併合
    if rank[lRoot] < rank[rRoot]:
      parent[lRoot] = rRoot
      pardist[lRoot] = dist + rPardist - lPardist
    else:
      parent[rRoot] = lRoot
      pardist[rRoot] = dist + lPardist - rPardist
      if rank[lRoot] == rank[rRoot]:
        rank[lRoot] += 1

for i in range(M):
  l, r, d = map(int, input().split())
  unite(l, r, d)

print('Yes')

Submission status: Wrong Answer

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

people = [0] * (N+1)
for l, r, d in LRD:
    if people[l] & people[r]:
        if abs(people[r]) + abs(people[l]) != d:
            print("No")
            break
    else:
        people[l] -= d
        people[r] += d
else:
    print("Yes")

Submission status: Wrong Answer

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

people = [0] * (N+1)
for l, r, d in LRD:
    if people[l] & people[r]:
        if abs(people[r]) + abs(people[l]) != d:
            print("No")
            break
    else:
        people[l] = -d
        people[r] = d
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))
    return 1

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[i] != False:
                if b[i] != c+d:
                    return False
            else:
                g(r,c+d)
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = [[] for _ in range(n)]
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[i] != False:
                if b[i] != c+d:
                    return False
            else:
                g(r,c+d)
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3

import array
import heapq
import itertools


MIN_X = 0
MAX_X = 10 ** 9


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


class TopologicalSortError(Exception):
    pass


def topological_sort(num_vs, adj_vs):
    """ Performs topological sorting of the given DAG.

    This function computes the lexicographically least
    topological order of the given DAG.

    :param num_vs int: The number of vertices.
    :param adj_vs list: The adjacency list.
    :return: The lexicographically least topological order.
    :rtype: :obj:`array.array`
    :raises TopologicalSortError: if the given graph is not a DAG
    """
    in_deg = array.array("L", (0 for _ in range(num_vs)))
    for dests in adj_vs:
        for dest in dests:
            in_deg[dest] += 1
    sorted_vs = array.array("L")
    pq = []
    for s in range(num_vs):
        if in_deg[s] == 0:
            heapq.heappush(pq, s)
    while pq:
        u = heapq.heappop(pq)
        sorted_vs.append(u)
        for v in adj_vs[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                heapq.heappush(pq, v)
    if all(x == 0 for x in in_deg):
        return sorted_vs
    else:
        raise TopologicalSortError("The graph has a cycle")


def solve(n, adj_vs, dist):
    uf_vs = UnionFind(n)
    try:
        sorted_vs = topological_sort(n, adj_vs)
    except TopologicalSortError:
        return False
    dist.sort(key=lambda p: (sorted_vs[p[0]], sorted_vs[p[1]]))
    xs = [None for _ in range(n)]
    xs[sorted_vs[0]] = 0
    for l, r, d in dist:
        uf_vs.unite(l, r)
        if xs[l] is None:
            xs[l] = 0
        if xs[r] is None:
            xs[r] = xs[l] + d
        else:
            if xs[r] - xs[l] != d:
                return False
    res = itertools.groupby(range(n), key=lambda x: uf_vs.par[x])
    for _, g in res:
        g2 = list(g)
        if max(g2) - min(g2) > (MAX_X - MIN_X):
            return False
    return True


def main():
    n, m = (int(x) for x in input().split())
    adj_vs = [set() for _ in range(n)]
    dist = []
    for _ in range(m):
        l, r, d = (int(x) for x in input().split())
        adj_vs[l - 1].add(r - 1)
        dist.append((l - 1, r - 1, d))
    print("Yes" if solve(n, adj_vs, dist) else "No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#def fun():
import bisect

[N,M]=map(int,raw_input().split())
A={}
K=[]
for i in range(1,N+1):
    A[i]=[]
bignum=-100000000000
C=[bignum for x in range(N+1)]
for i in range(M):
    [L,R,D]=map(int,raw_input().split())
    A[L].append([R,D])
    A[R].append([L,-D])
    if L not in K:
        K.append(L)
    if R not in K:
        K.append(R)
#K=A.keys()
K.sort
E=[]
flg=1
while len(K)!=0 or len(E)!=0:
    if len(E)==0:
        k=K.pop(0)
        C[k]=0
    else:
        k=E.pop(0)
    a=A[k]
    for aa in a:
        [n,d]=aa
        if C[n]!=bignum and C[n]!=C[k]+d:
            print "No"
            flg=0
        else:
            C[n]=C[k]+d
        id =min(bisect.bisect_left(K,n),len(K))
        if len(K)!=0 and K[id]==n:
            K=K[:id]+K[id+1:]
            E.append(n)
    if not flg:
        break
if flg:
    print "yes"

Submission status: Wrong Answer

Solution code:
import sys


class UnionFind:
    def __init__(self, MAX_N):
        self.parent = [i for i in range(MAX_N)]
        self.rank = [0 for _ in range(MAX_N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.rank[x] += 1

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


N, M = map(int, input().split())
L = []
R = []
D = []

uf = UnionFind(N+1)

for i in range(M):
    l, r, d = map(int, input().split())
    L.append(l)
    R.append(r)
    D.append(d)

    if uf.same(l, r):
        if True:
            print('No')
            exit()
    else:
        uf.unite(l, r)

print('Yes')

Submission status: Wrong Answer

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

rights = [{} for _ in range(N)]

for m in range(M):
    L, R, D = map(int, input().split())
    rights[L-1][R-1] = D

for l in range(N):
    for r, d in rights[l].items():
        for s, e in rights[r].items():
            if s in rights[l] and  rights[l][s] != d + e:
                print('No')
                sys.exit()
            if l in rights[s] and rights[s][l] != d + e:
                print('No')
                sys.exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
if M == 0:
	print('Yes')
	exit()
man = [None for i in range(N)]
info = []
for i in range(M):
	L,R,D  = map(int,input().split())
	if L > R:
		L,R,D = R,L,-D
	info.append((L-1,R-1,D))


info.sort()
man[info[0][0]] = 0
flag = True
for (l,r,d) in info:
	if man[l] == None:
		if man[r] != None:
			man[l] = man[r] - d
		else:
			continue
	if man[r] != None:
		if man[l] + d != man[r]:
			flag = False
			break
	else:
		man[r] = man[l] + d

for (l,r,d) in info:
	if man[l] == None:
		if man[r] != None:
			man[l] = man[r] - d
		else:
			man[l] = 0
	if man[r] != None:
		if man[l] + d != man[r]:
			flag = False
			break
	else:
		man[r] = man[l] + d

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()
man = [None for i in range(N)]
info = []
for i in range(M):
	L,R,D  = map(int,input().split())
	if L > R:
		L,R,D = R,L,-D
	info.append((L-1,R-1,D))


info.sort()
man[info[0][0]] = 0
flag = True
for (l,r,d) in info:
	if man[l] == None:
		if man[r] != None:
			man[l] = man[r] - d
		else:
			continue
	if man[r] != None:
		if man[l] + d != man[r]:
			flag = False
			break
	else:
		man[r] = man[l] + d

for (l,r,d) in info:
	if man[l] == None:
		man[l] = 0
	if man[r] != None:
		if man[l] + d != man[r]:
			flag = False
			break
	else:
		man[r] = man[l] + d

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
people_location = []
for i in range(N):
    people_location.append(0)
people_data = []
for i in range(M):
    person_data = list(map(int, input().split()))
    if person_data[0] > person_data[1]:
        tmp = person_data[0]
        person_data[0] = person_data[1]
        person_data[1] = tmp
        person_data[2] = 0 - person_data[2]
    people_data.append(person_data)
people_data.sort()
for i in range(M):
    local_tmp = people_location[people_data[i][0] - 1] + people_data[i][2]
    if people_location[people_data[i][1] - 1] == 0:
        people_location[people_data[i][1] - 1] = local_tmp
    elif people_location[people_data[i][1] - 1] != local_tmp:
        print("No")
        break
else:
    print("Yes")

Submission status: Wrong Answer

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

l, r, d = [], [], []

for i in range(m):
    l_, r_, d_ = map(int, input().split())
    if l_ < r_:
        l.append(l_-1)
        r.append(r_-1)
        d.append(d_)
    else:
        l.append(r_-1)
        r.append(l_-1)
        d.append(-d_)

import numpy as np
arg = np.argsort(l)

l, r, d = np.array(l)[arg], np.array(r)[arg], np.array(d)[arg]
p = [None for i in range(n)]

def solve():

    if m == 0:
        print("Yes")
        return

    for i in range(m):
        if p[l[i]] is None and p[r[i]] is None:
            # initialize
            p[l[i]] = 0
            p[r[i]] = d[i]
        elif p[l[i]] is None:
            # add rule
            p[l[i]] = p[r[i]] - d[i]
        elif p[r[i]] is None:
            # add rule
            p[r[i]] = p[l[i]] + d[i]
        else:
            # check rule
            if p[r[i]] - p[l[i]] != d[i]:
                print("No")
                return

    # check max position
    if max(p) - min(p) > 10**9:
        print("No")
    else:
        print("Yes")

solve()

Submission status: Wrong Answer

Solution code:
def solve(N, M, lrd):
    xss = []
    def getx(n):
        for xs in xss:
            if n in xs:
                return xs
        xs = {n: 0}
        xss.append(xs)
        return xs
    for l, r, d in lrd:
        lxs = getx(l)
        rxs = getx(r)
        if lxs is rxs:
            if lxs[l] != rxs[r] - d:
                return 0
        else:
            delta = lxs[l] - rxs[r] - d
            for k in lxs:
                v = lxs[k] + delta
                if k in rxs:
                    if rxs[k] != v:
                        return 0
                rxs[k] = v
            xss.remove(lxs)
    for xs in xss:
        if max(xs.values()) - min(xs.values()) > 10**9:
            return 0
    return 1

N, M = [int(x) for x in input().split()]
lrd = []
for i in range(M):
    lrd.append([int(x) for x in input().split()])

#N, M = 3, 3
#lrd = [[1,2,1],[2,3,1],[1,3,2]]

#N, M = 4, 3
#lrd = [[2,1,1],[2,3,5],[3,4,2]]

#N, M = 10, 3
#lrd = [[8,7,100],[7,9,100],[9,8,100]]

#N, M = 100, 0
#lrd = []

if solve(N, M, lrd):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
"""
Example: 

from/to
1 [ -  1  2]
2 [-1  -  1]
3 [-2 -1  -]
"""

N, M = [int(x) for x in input().split()]


to_list = [{} for _ in range(N)]
for _ in range(M):
    L, R, D = [int(x) for x in input().split()]
    L = L - 1
    R = R - 1
    if (L, R) in to_list[R].keys() and to_list[R][(L, R)] != D:
        print("No")
        exit()
    if (R, L) in to_list[L].keys() and to_list[L][(R, L)] != -D:
        print("No")
        exit()

    to_list[R][(L, R)] = D
    to_list[L][(R, L)] = -D

    for k, v in to_list[L].items():
        _L, _ = k
        to_list[R][(_L, R)] = D + v

    for k, v in to_list[R].items():
        _R, _ = k
        to_list[L][(_R, L)] = -D + v

# print(to_list)
print("Yes")