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 = list(map(int, input().split()))
Llist = []
Rlist = []
Dlist = []
for i in range(M):
    l, r, d = input().split()
    Llist.append(l)
    Rlist.append(r)
    Dlist.append(int(d))

#
mat = {}

#
def exist(i, j):
    if j<i:
        i,j = j,i
    if not i in mat:
        return False
    if not j in mat[i]:
        return False
    return True
#
def get(i, j):
    if j<i:
        return -mat[j][i]
    else:
        return mat[i][j]

#
def add(i, j, k):
    if j<i:
        i,j = j,i
        k = -k
    if exist(i, j) or i in mat:
        mat[i][j] = k
    else:
        mat[i] = {j : k}

#
for i in range(M):
    L = Llist[i]
    R = Rlist[i]
    D = Dlist[i]

    # first check
    if exist(L, R) and get(L, R)!=D:
        print('No')
        exit()

    # add
    add(L, R, D)
    #print('add', L, R, D)

    # check
    if L in mat:
        for X in mat[L]:
            if X!=R:
                x = get(L, R) - get(L, X)
                #print('LR', get(L, R), 'LX', get(L, X), 'XR', x)
                if exist(R, X) and get(X, R)!=x:
                    print('No')
                    exit()
                else:
                    add(X, R, x)

    if R in mat:
        for X in mat[R]:
            if X!=L:
                x = get(L, R) + get(R, X)
                #print('LR', get(L, R), 'RX', get(R, X), 'LX', x)
                if exist(L, X) and get(L, X)!=x:
                    print('No')
                    exit()
                else:
                    add(L, X, x)

print('Yes')

Submission status: Wrong Answer

Solution code:
#
N, M = list(map(int, input().split()))
Llist = []
Rlist = []
Dlist = []
for i in range(M):
    l, r, d = input().split()
    Llist.append(l)
    Rlist.append(r)
    Dlist.append(int(d))

#
mat = {}

#
def exist(i, j):
    if j<i:
        i,j = j,i
    if not i in mat:
        return False
    if not j in mat[i]:
        return False
    return True
#
def get(i, j):
    if j<i:
        return -mat[j][i]
    else:
        return mat[i][j]

#
def add(i, j, k):
    if j<i:
        i,j = j,i
        k = -k
    if exist(i, j) or i in mat:
        mat[i][j] = k
    else:
        mat[i] = {j : k}

#
for i in range(M):
    L = Llist[i]
    R = Rlist[i]
    D = Dlist[i]

    # first check
    if exist(L, R) and get(L, R)!=D:
        print('No')
        exit()

    # add
    add(L, R, D)
    #print('add', L, R, D)

    # check
    if L in mat:
        for X in mat[L]:
            if X!=R:
                x = get(L, R) - get(L, X)
                #print('LR', get(L, R), 'LX', get(L, X), 'XR', x)
                if exist(R, X) and get(R, X)!=x:
                    print('No')
                    exit()
                else:
                    add(X, R, x)

    if R in mat:
        for X in mat[R]:
            if X!=L:
                x = get(L, R) + get(R, X)
                #print('LR', get(L, R), 'RX', get(R, X), 'LX', x)
                if exist(L, X) and get(L, X)!=x:
                    print('No')
                    exit()
                else:
                    add(L, X, x)

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 = defaultdict(lambda: 0)
	memo = defaultdict(lambda: False)
	f = True
	tmp = []


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

		if abs(l-r) == 1:
			dist[(l,r)] = d
			dist[(r,l)] = d
			memo[(l,r)] = True
			memo[(r,l)] = True


		else:
			tmp.append([l,r,d])



	for t in tmp:
		l,r,d = t

		diff = 0
		s = True

		for i in range(l+1,r+1):
			if memo[(i-1,i)]:
				diff += dist[i-1,i]
			else:
				s = False
				break

		if diff != 0:
			if s:
				if diff != 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:
#
N, M = list(map(int, input().split()))
Llist = []
Rlist = []
Dlist = []
for i in range(M):
    l, r, d = input().split()
    Llist.append(l)
    Rlist.append(r)
    Dlist.append(int(d))

#
mat = {}

#
def exist(i, j):
    if j<i:
        i,j = j,i
    if not i in mat:
        return False
    if not j in mat[i]:
        return False
    return True
#
def get(i, j):
    if j<i:
        return mat[j][i]
    else:
        return mat[i][j]

#
def add(i, j, k):
    if j<i:
        i,j = j,i
        k = -k
    if exist(i, j) or i in mat:
        mat[i][j] = k
    else:
        mat[i] = {j : k}

#
for i in range(M):
    L = Llist[i]
    R = Rlist[i]
    D = Dlist[i]

    # first check
    if exist(L, R) and get(L, R)!=D:
        print('No')
        exit()

    # add
    add(L, R, D)
    #print('add', L, R, D)

    # check
    if L in mat:
        for X in mat[L]:
            if X!=R:
                x = get(L, R) - get(L, X)
                #print('LR', get(L, R), 'LX', get(L, X), 'RX', x)
                if exist(R, X) and get(R, X)!=x:
                    print('No')
                    exit()
                else:
                    add(R, X, x)

    if R in mat:
        for X in mat[R]:
            if X!=L:
                x = get(L, R) + get(R, X)
                #print('LR', get(L, R), 'RX', get(R, X), 'LX', x)
                if exist(L, X) and get(L, X)!=x:
                    print('No')
                    exit()
                else:
                    add(L, X, x)

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
		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
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 and max(man) - min(man) <= 10**9:
	print('Yes')
else:
	print('No')

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 i, t in enumerate(lrd):
        if t[0] > t[1]:
            lrd[i] = (t[1], t[0], -t[2])
        else:
            lrd[i] = (t[0], t[1], t[2])
    for l, r, d in sorted(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 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 = defaultdict(lambda: 0)
	memo = defaultdict(lambda: False)
	f = True
	tmp = []


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

		if abs(l-r) == 1:
			dist[(l,r)] = d
			dist[(r,l)] = d
			memo[(l,r)] = True
			memo[(r,l)] = True


		else:
			tmp.append([l,r,d])



	for t in tmp:
		l,r,d = t


		diff = 0
		rest = False

		for i in range(l+1,r+1):
			if memo[(i-1,i)]:
				diff += dist[i-1,i]
			else:
				rest = True

		if diff != 0:
			if not rest:
				if diff != d:
					f = False
					break
			else:
				if diff > 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()
    e = collections.defaultdict(list)
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

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

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]
LRD.sort(key=lambda x:x[0]or x[1])

people = [0] * (N+1)
peetru = [False] * (N+1)
for l, r, d in LRD:
    if (peetru[l]) & (peetru[r]):
        if abs(people[r]- people[l]) != d:
            print("No")
            break
    else:
        peetru[l] = True
        peetru[r] = True
        people[l] = -1*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
		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
man = [m for m in man if m != None]
if flag and max(man) - min(man) <= 10**9:
	print('Yes')
else:
	print('No')

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()
    e = collections.defaultdict(list)
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

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

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

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]



def solve():
    p = np.array([np.nan for i in range(n)])
    blanches = np.array([-1 for i in range(n)])
    n_blanches = -1

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

    for i in range(m):
        if np.isnan(p[l[i]]) and np.isnan(p[r[i]]):
            # create isolate blanch
            n_blanches += 1
            blanches[l[i]] = n_blanches
            blanches[r[i]] = n_blanches
            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]
            blanches[l[i]] = blanches[r[i]]

        elif np.isnan(p[r[i]]):
            # add rule
            p[r[i]] = p[l[i]] + d[i]
            blanches[r[i]] = blanches[l[i]]

        else:
            # check merge
            if blanches[r[i]] == blanches[l[i]]:
                # check rule
                if p[r[i]] - p[l[i]] != d[i]:
                    print("No")
                    return
            else:
                # merge
                adj = p[r[i]] - p[l[i]] + d[i]
                p[blanches==blanches[r[i]]] += adj
                blanches[blanches==blanches[r[i]]] = blanches[l[i]]

    # 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:
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]



def solve():
    p = np.array([np.nan for i in range(n)])
    blanches = np.array([-1 for i in range(n)])
    n_blanches = -1

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

    for i in range(m):
        if np.isnan(p[l[i]]) and np.isnan(p[r[i]]):
            # create isolate blanch
            n_blanches += 1
            blanches[l[i]] = n_blanches
            blanches[r[i]] = n_blanches
            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]
            blanches[l[i]] = blanches[r[i]]

        elif np.isnan(p[r[i]]):
            # add rule
            p[r[i]] = p[l[i]] + d[i]
            blanches[r[i]] = blanches[l[i]]

        else:
            # check merge
            if blanches[r[i]] == blanches[l[i]]:
                # check rule
                if p[r[i]] - p[l[i]] != d[i]:
                    print("No")
                    return
            else:
                # merge
                adj = p[r[i]] - p[l[i]] + d[i]
                p[blanches==blanches[r[i]]] += adj
                blanches[blanches==blanches[r[i]]] = blanches[l[i]]
    print(p)
    print(blanches)
    # 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:
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 sorted(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:
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 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 = defaultdict(lambda: 0)
	f = True
	tmp = []

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

		if abs(l-r) == 1:
			dist[(l,r)] = d
			dist[(r,l)] = d

		else:
			tmp.append([l,r,d])

	for t in tmp:
		l,r,d = t

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



def solve():
    p = np.array([np.nan for i in range(n)])
    blanches = np.array([-1 for i in range(n)])
    n_blanches = -1

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

    for i in range(m):
        if np.isnan(p[l[i]]) and np.isnan(p[r[i]]):
            # create isolate blanch
            n_blanches += 1
            blanches[l[i]] = n_blanches
            blanches[r[i]] = n_blanches
            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]
            blanches[l[i]] = blanches[r[i]]

        elif np.isnan(p[r[i]]):
            # add rule
            p[r[i]] = p[l[i]] + d[i]
            blanches[r[i]] = blanches[l[i]]

        else:
            # check merge
            if blanches[r[i]] == blanches[l[i]]:
                # check rule
                if p[r[i]] - p[l[i]] != d[i]:
                    print("No")
                    return
            else:
                # merge
                adj = p[r[i]] - p[l[i]] + d[i]
                p[blanches==blanches[r[i]]] -= adj
                blanches[blanches==blanches[r[i]]] = blanches[l[i]]

    # 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
N, M = map(int, input().split())
if M == 0:
    print('Yes')
    sys.exit()
m = []
for i in range(M):
    m.append(list(map(int, input().split())))
x = [None for i in range(N)]

def which_set(l, index):
    for i, ll in enumerate(l):
        if index in ll:
            return i
    return -1

lines = [set((m[0][0]-1, m[0][1]-1))]
x[m[0][0]-1] = 0
x[m[0][1]-1] = m[0][2]
for mm in m[1:]:
    l_set = which_set(lines, mm[0]-1)
    r_set = which_set(lines, mm[1]-1)
    if r_set >= 0 and l_set >=0 and r_set == l_set:
        if x[mm[1]-1] - x[mm[0]-1] == mm[2]:
            pass
        else:
            print('No')
            sys.exit()
    elif l_set >= 0 and r_set < 0:
        lines[l_set].add(mm[1]-1)
        x[mm[1]-1] = x[mm[0]-1] + mm[2]		
    elif l_set < 0 and r_set >= 0:
        lines[r_set].add(mm[0]-1)
        x[mm[0]-1] = x[mm[1]-1] - mm[2]
    elif r_set >= 0 and l_set >=0:
        lines[r_set] = lines[r_set] | lines[l_set]
        d = x[mm[1] -1] - x[mm[0]-1]
        for i in lines[l_set]:
            x[i] = x[i] - d
        del lines[l_set]
    else:
        lines.append(set((mm[0]-1, mm[1]-1)))
        x[mm[0]-1] = 0
        x[mm[1]-1] = mm[2]

print('Yes')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]
LRD.sort(key=lambda x:x[0]or x[1])

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:
import sys
N, M = map(int, input().split())
if M == 0:
    print('Yes')
    sys.exit()
m = []
for i in range(M):
    m.append(list(map(int, input().split())))
x = [None for i in range(N)]

def which_set(l, index):
    for i, ll in enumerate(l):
        if index in ll:
            return i
    return -1

lines = [set((m[0][0]-1, m[0][1]-1))]
x[m[0][0]-1] = 0
x[m[0][1]-1] = m[0][2]
for mm in m[1:]:
    l_set = which_set(lines, mm[0]-1)
    r_set = which_set(lines, mm[1]-1)
    if r_set >= 0 and l_set >=0 and r_set == l_set:
        if x[mm[1]-1] - x[mm[0]-1] == mm[2]:
            pass
        else:
            print('No')
            sys.exit()
    elif l_set >= 0 and r_set < 0:
        lines[l_set].add(mm[1]-1)
        x[mm[1]-1] = x[mm[0]-1] + mm[2]		
    elif l_set < 0 and r_set >= 0:
        lines[r_set].add(mm[0]-1)
        x[mm[0]-1] = x[mm[1]-1] - mm[2]
    elif r_set >= 0 and l_set >=0:
        lines[r_set] = lines[r_set] | lines[l_set]
        d = x[mm[1] -1] - x[mm[0]-1]
        for i in lines[l_set]:
            x[i] += x[i] - d
        del lines[l_set]
    else:
        lines.append(set((mm[0]-1, mm[1]-1)))
        x[mm[0]-1] = 0
        x[mm[1]-1] = mm[2]

print('Yes')

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.825:
            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())