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: Runtime Error

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]
        r_gp=gp[r-1]
        l_x=x[l-1]
        for i in range(M):
            if(gp[i]==r_gp):
                x[i]+=d+l_x
            if(gp[i]==from_gp):
                gp[i]=to_gp
        if(max(x)>10**9):
            print('No')
            break
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
import numpy as np
pos = [[] for i in range(100000)]
qe = []
n, m = map(int, input().split())
if m == 0:
    print("Yes")
    exit()
posvis = np.array([[1] for i in range(100000)])
posit = [[] for i in range(200000)]
l, r, d = map(int, input().split())
pos[l].append([r, d, 0])
pos[r].append([l, -d, 0])
qe.append([l, r, d])
mem = set([])
por = [[] for i in range(200000)]
for i in range(1, m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])
    mem.add(l)
    mem.add(r)
def deep(self, vis = 0):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if not vis:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
            # try:
                por[j[0]].append(por[self][0] + j[1])
                # [posit.index(self) + j[1]].append(j[0])
            # except:
            por[j[0]].append(por[self][0] + j[1])
                # posit[100000] = [self]
                # posit[posit.index([self]) + j[1]].append(j[0])
            deep(j[0], 1)
for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

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].add(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: Runtime Error

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 solve0(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

def solve(N, M, lrd):
    uf = UnionFind(N + 1)
    for l, r, d in lrd:
        uf.union(l, r)
    xs = {}
    for i, n in enumerate(uf.table):
        if i == 0:
            continue
        if n >= 0:
            n = uf.table[n]
        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

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 = 3, 3
#lrd = [[1,2,1],[2,3,1],[1,3,5]]

#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: Runtime Error

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)

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: Runtime Error

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


def dfs(x, ls, rs, pos):
    xpos = 0 if pos[x] is None else pos[x]
    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: Runtime Error

Solution code:
import sys
from collections import defaultdict

N, M = map(int, sys.stdin.readline().split())
E = defaultdict(list)

for _ in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    l -= 1
    r -= 1
    E[l].append((r, d))
    E[r].append((l, -d))

xs = [None] * N

def dfs(i, x):
    xs[i] = x
    mi, ma = x, x
    for j, d in E[i]:
        if xs[j] is None:
            res = dfs(j, x + d)
            if res is None:
                return None
            else:
                mi2, ma2 = res
                mi = min(mi2, mi)
                ma = max(ma2, ma)
        else:
            if xs[j] - x != d:
                return None
    return mi, ma

for i in range(N):
    if xs[i] is None:
        res = dfs(i, 0)
        if res is None:
            break
        else:
            mi, ma = res
            if ma - mi > 1e9:
                break
else:
    print('Yes')
    sys.exit()
print('No')

Submission status: Runtime Error

Solution code:
#def fun():
import bisect

[N,M]=map(int,raw_input().split())
A={}
B={}
for i in range(1,N+1):
    A[i]=[]
    B[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])
K=A.keys()
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]+B[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 K[id]==n:
            K=K[:id]+K[id+1:]
            E.append(n)
    if not flg:
        break
if flg:
    print "yes"

Submission status: Runtime Error

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
	group[R] = L
	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
	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: Runtime Error

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 = collections.defaultdict(list)
    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 b[i] != False:
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            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: Runtime Error

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[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: Runtime Error

Solution code:
def check(i, xs):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for jc in children:
        if not check(jc, xs):
            return False
    return True


def solve():
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs)
            if not res:
                return False
            xf = list(filter(lambda x: x is not None, xs))
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
checked = set()
print('Yes' if solve() else 'No')

Submission status: Runtime Error

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

bio = [None for i in range(n)]
def dfs(x):
    for y, d in a[x]:
        if bio[y] is None:
            bio[y] = bio[x] + d
            if not dfs(y):
                return False
        elif bio[y] != bio[x] + d:
            return False
    return True

for i in range(n):
    if bio[i] is None:
        bio[i] = 0
        if not dfs(i):
            print('No')
            exit(0)
print('Yes')