Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

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

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

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

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

D_i are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

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

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

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

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



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


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lrd = [list(map(int, input().split())) for _ in range(m)]


class WeightedUnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x
        self.weight = [0] * x

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v, w):
        self.link(self.find_set(u), self.find_set(v), w)

    def find_set(self, u):
        if u != self.p[u]:
            v = self.find_set(self.p[u])
            self.weight[u] += self.weight[self.p[u]]
            self.p[u] = v

        return self.p[u]

    def link(self, u, v, w):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.weight[v] = w - self.weight[u] + self.weight[v]
        else:
            self.p[u] = v
            self.weight[u] = -w - self.weight[v] + self.weight[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def get_weight(self, u):
        self.find_set(u)
        return self.weight[u]

    def diff(self, u, v):
        return self.get_weight(u) - self.get_weight(v)


wuf = WeightedUnionFind(n)

for l, r, d in lrd:
    l -= 1
    r -= 1

    if wuf.same(l, r):
        if wuf.diff(r, l) != d:
            print("No")
            exit()

    else:
        wuf.unite(l, r, d)

print("Yes")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lrd = [list(map(int, input().split())) for _ in range(m)]


class WeightedUnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x
        self.weight = [0] * x

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v, w):
        self.link(self.find_set(u), self.find_set(v), w)

    def find_set(self, u):
        if u != self.p[u]:
            v = self.find_set(self.p[u])
            self.weight[u] += self.weight[self.p[u]]
            self.p[u] = v

        return self.p[u]

    def link(self, u, v, w):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.weight[v] = w - self.weight[u] + self.weight[v]
        else:
            self.p[u] = v
            self.weight[u] = -w - self.weight[v] + self.weight[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def get_weight(self, u):
        self.find_set(u)
        return self.weight[u]

    def diff(self, u, v):
        return self.get_weight(u) - self.get_weight(v)


wuf = WeightedUnionFind(n)

for l, r, d in lrd:
    l -= 1
    r -= 1

    if wuf.same(l, r):
        if wuf.diff(r, l) != d:
            print(l, r, d, wuf.diff(r, l))
            print("No")
            exit()

    else:
        wuf.unite(l, r, d)

print("Yes")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lrd = [list(map(int, input().split())) for _ in range(m)]


class UnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x
        self.d = [0] * x

    def same(self, u, v):
        du, pu = self.find_set(u)
        dv, pv = self.find_set(v)
        return pu == pv, self.d[v] - self.d[u]

    def unite(self, u, v, dist):
        self.link(self.find_set(u), self.find_set(v), dist)

    def find_set(self, u):
        if u != self.p[u]:
            d, self.p[u] = self.find_set(self.p[u])
            self.d[u] += d

        return self.d[u], self.p[u]

    def link(self, fsu, fsv, dist):
        du, u = fsu
        dv, v = fsv
        self.p[v] = u
        self.d[v] = du + dist


uf = UnionFind(n)

for l, r, d in lrd:
    l -= 1
    r -= 1

    bl, dist = uf.same(l, r)
    #print(bl, d, dist, uf.d)

    if bl:
        if d != dist:
            print("No")
            exit()

    else:
        uf.unite(l, r, d)

d_mn = float("inf")
d_mx = 0
for i in range(n):
    d = uf.d[i]
    d_mn = min(d_mn, d)
    d_mx = max(d_mx, d)

if d_mx - d_mn > 10 ** 9:
    ans = "No"
else:
    ans = "Yes"

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lrd = [list(map(int, input().split())) for _ in range(m)]


class UnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x
        self.d = [0] * x

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v), self.d[u] + self.d[v]

    def unite(self, u, v, dist):
        self.link(self.find_set(u), self.find_set(v), dist)

    def find_set(self, u):
        if u != self.p[u]:
            d, self.p[u] = self.find_set(self.p[u])
            self.d[u] += d

        return self.d[u], self.p[u]

    def link(self, fsu, fsv, dist):
        du, u = fsu
        dv, v = fsv
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.d[v] = self.d[u] + dist
        else:
            self.p[u] = v
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1
            self.d[u] = self.d[v] + dist


uf = UnionFind(n)

for l, r, d in lrd:
    l -= 1
    r -= 1

    bl, dist = uf.same(l, r)

    if bl:
        if d != dist:
            print("No")
            exit()

    else:
        uf.unite(l, r, d)

d_mn = 0
d_mx = 0
for i in range(n):
    d = uf.d[i]
    d_mn = min(d_mn, d)
    d_mx = max(d_mx, d)

if d_mx - d_mn > 10 ** 9:
    ans = "No"
else:
    ans = "Yes"

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lrd = [list(map(int, input().split())) for _ in range(m)]


class UnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x
        self.d = [0] * x

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v), self.d[u] + self.d[v]

    def unite(self, u, v, dist):
        self.link(self.find_set(u), self.find_set(v), dist)

    def find_set(self, u):
        if u != self.p[u]:
            d, self.p[u] = self.find_set(self.p[u])
            self.d[u] += d

        return self.d[u], self.p[u]

    def link(self, fsu, fsv, dist):
        du, u = fsu
        dv, v = fsv
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.d[v] = self.d[u] + dist
        else:
            self.p[u] = v
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1
            self.d[u] = self.d[v] + dist


uf = UnionFind(n)

for l, r, d in lrd:
    l -= 1
    r -= 1

    bl, dist = uf.same(l, r)

    if bl:
        if d != dist:
            print("No")
            exit()

    else:
        uf.unite(l, r, d)

print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start):
    while graph != {}:
        start = min(graph.keys())
        queue = deque([])
        queue.append(start)
        pos = {}
        pos[start] = 0

        while queue:
            u = queue.popleft()
            for v,d in graph[u].items():
                if v not in pos:
                    pos[v] = pos[u] + d
                    if v in graph:
                        queue.append(v)
                elif pos[v] != pos[u] + d:
                    return False
            del graph[u]
            # print(queue)
        return True

n,m = map(int, input().split())

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')
# print(graph)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start):
    while graph != {}:
        start = min(graph.keys())
        queue = deque([])
        queue.append(start)
        pos = {}
        pos[start] = 0

        while queue:
            u = queue.popleft()
            for v,d in graph[u].items():
                if v not in pos:
                    pos[v] = pos[u] + d
                    if v in graph:
                        queue.append(v)
                elif pos[v] != pos[u] + d:
                    return False
            del graph[u]
            # print(queue)
        return True

n,m = map(int, input().split())

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')
print(graph)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start):
    while graph:
        start = min(graph.keys())
        queue = deque([])
        queue.append(start)
        pos = {}
        pos[start] = 0

        while queue:
            u = queue.popleft()
            if u not in graph:
                continue
            for v,d in graph[u].items():
                if v not in pos:
                    pos[v] = pos[u] + d
                    queue.append(v)
                elif pos[v] != pos[u] + d:
                    return False
            del graph[u]
            # print(queue)
        return True

n,m = map(int, input().split())

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start):
    queue = deque([])
    queue.append(start)
    pos = {}
    pos[start] = 0

    while queue:
        u = queue.popleft()
        if u not in graph:
            if graph != {}:
                u = min(graph.keys())
                pos = {u:0}
            else:
                continue
        for v,d in graph[u].items():
            if v not in pos:
                pos[v] = pos[u] + d
                queue.append(v)
            elif pos[v] != pos[u] + d:
                return False
        del graph[u]
        # print(queue)
    return True

n,m = map(int, input().split())

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start):
    queue = deque([])
    queue.append(start)
    pos[start] = 0

    while queue:
        u = queue.popleft()
        for v,d in graph[u].items():
            if v not in pos:
                pos[v] = pos[u] + d
                queue.append(v)
            elif pos[v] != pos[u] + d:
                return False
        # print(queue)
    return True

n,m = map(int, input().split())

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

pos = {}
if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')

# print(graph)
# print(pos)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start):
    queue = deque([])
    queue.append(start)
    pos[start] = 0
    dis = {0:start}
    mx = 0
    mn = 0
    mod = 10**9

    while queue:
        u = queue.popleft()
        if u not in graph:
            continue
        for v,d in graph[u].items():
            if v not in pos:
                pos[v] = pos[u] + d
                dis[pos[u] + d] = v
                queue.append(v)
                if pos[u] + d > mx:
                    mx = pos[u] + d
                    if mx - mn > mod:
                        return False
            elif pos[v] != pos[u] + d:
                return False
        # print(queue)
    return True

n,m = map(int, input().split())

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d

pos = {}
if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')

# print(graph)
# print(pos)

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.parents[rx] > self.parents[ry]:
            self.parents[ry] += self.parents[rx]
            self.parents[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.parents[rx] += self.parents[ry]
            self.parents[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]

    def find_position(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return -self.weight[x] + self.find_position(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.find_position(y) - self.find_position(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.parents[rx] > self.parents[ry]:
            rx, ry = ry, rx
            x, y = y, x
            w = -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = self.weight[x] - w - self.weight[y]

    def find_position(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return -self.weight[x] + self.find_position(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.find_position(y) - self.find_position(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    right = 0
    left = 0
    for i in range(N):
        pos = uf.weight[i]
        right = max(right, pos)
        left = min(left, pos)
        if right - left > 10 ** 9:
            res = 'No'
        else:
            res = 'Yes'

print(res)

Submission status: Wrong Answer

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.parents[rx] > self.parents[ry]:
            rx, ry = ry, rx
            x, y = y, x
            w = -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = + self.weight[x] - w - self.weight[y]

    def find_position(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return -self.weight[x] + self.find_position(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.find_position(y) - self.find_position(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
ans = {}
LRD = []
for _ in range(M):
  l,r,d = map(int,input().split())
  LRD.append([l,d,r])
LRD.sort()

for i in range(M):
  l,d,r = LRD[i]
  if i == 0:
    ans[l] = 0
    ans[r] = d
  elif l in ans and r in ans:
    if ans[l]+d != ans[r]:
      print('No')
      exit()
  elif l in ans:
    ans[r] = ans[l]+d
  elif r in ans:
    ans[l] = ans[r]-d

print('Yes')

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
ans = {}
LRD = [list( map(int,input().split())) for _ in range(M)]
LRD.sort()

for i in range(M):
  l,r,d = LRD[i]
  if i == 0:
    ans[l] = 0
    ans[r] = d
  elif l in ans and r in ans:
    if ans[l]+d != ans[r]:
      print('No')
      exit()
  elif l in ans:
    ans[r] = ans[l]+d
  elif r in ans:
    ans[l] = ans[r]-d

print('Yes')

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
ans = {}
for _ in range(M):
  l,r,d = map(int,input().split())
  if l not in ans:
    ans[l] = 0
    ans[r] = d
  else:
    if r in ans:
      if ans[l]+d != ans[r]:
        print('No')
        exit()
    else:
      ans[r] = ans[l]+d
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[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 diff_w(self, x, y):
        return self.weight[x] - self.weight[y]


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        if d != D.diff_w(l, r):
            print('No')
            sys.exit()
    
    print('Yes')


main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[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)

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


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for i in range(N):
        D.find(i)

    for i in set(D.par):
        if D.weight[i] != 0:
            print('No')
            sys.exit()

    print('Yes')


main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[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)

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


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for i in range(N):
        D.find(i)

    for i in set(D.par):
        if D.weight[i] != 0:
            print('No')
            sys.exit()

    print('Yes')


main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[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)

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


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for i in set(D.par):
        D.find(i)
        if D.weight[i] != 0:
            print('No')
            sys.exit()

    print('Yes')


main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


class WeightedUnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0] * N
        self.weight = [0] * N  # 親までの距離

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

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = -w - self.weight[x] + self.weight[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)

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


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    LRD = list(zip(m, m, m))

    D = WeightedUnionFind(N)

    for l, r, d in LRD:
        l -= 1
        r -= 1
        D.union(l, r, d)

    for i in D.par:
        if D.weight[i] != 0:
            print('No')
            sys.exit()

    print('Yes')


main()

Submission status: Wrong Answer

Solution code:
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 unite(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())
uf = WeightedUnionFind(n)
inf = []
for _ in range(m):
    l, r, d = map(int, input().split())
    inf.append((l, r, d))
    uf.unite(l, r, d)
# print(uf.weight)
for l, r, d in inf:
    if uf.diff(l, r) != d:
        print('No')
        exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
class UnionFindW():
    def __init__(self, n):
        self.tree = [i for i in range(n)]
        self.rank = [0]*n
        self.weight = [0]*n

    def root(self, x):
        if(self.tree[x] == x):
            return x
        self.tree[x] = self.root(self.tree[x])
        self.weight[x] += self.weight[self.tree[x]]
        return self.tree[x]  # 経路圧縮

    def same(self, x, y):  # xとyが同じ木に属するか
        return self.root(x) == self.root(y)

    def unite(self, x, y, w):
        nx = self.root(x)
        ny = self.root(y)
        if self.rank[nx] < self.rank[ny]:  # xの木の高さ>yの木の高さ
            self.tree[nx] = ny
            self.weight[nx] = w-self.weight[x]+self.weight[y]
        else:
            self.tree[ny] = nx
            self.weight[ny] = -w-self.weight[y]+self.weight[x]
            if self.rank[nx] == self.rank[ny]:
                self.rank[nx] += 1

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


n, m = map(int, input().split())
uf = UnionFindW(n)
inf = []
for _ in range(m):
    l, r, d = map(int, input().split())
    inf.append((l-1, r-1, d))
    uf.unite(l-1, r-1, d)
# print(uf.weight)
for l, r, d in inf:
    if uf.diff(l, r) != d:
        print('No')
        exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
def resolve():

    N,M = map(int,input().split())
    root = list(range(N))
    depth = [1 for _ in range(N)]
    dist = [0 for _ in range(N)]

    def find(a,root,dist):
        if root[a] == a:
            return (a,0)
        else:
            root[a],d = find(root[a],root,dist)
            dist[a] += d
            return(root[a],dist[a])

    def unite(a,b,d,root,depth,dist):
        A,dist_a = find(a,root,dist)
        B,dist_b = find(b,root,dist)
    #   print("a:{} A:{} dist_a:{}".format(a,A,dist_a))
    #   print("b:{} B:{} dist_b:{}".format(b,B,dist_b))

        if A == B:
            if dist_b - dist_a == d:
                return True
            else:
                return False
        else:
            if depth[A] > depth[B]:
                root[B] = A
                depth[A] += depth[B]
                dist[B] = dist_a - dist_b + d
            else:
                root[A] = B
                depth[B] += depth[A]
                dist[A] = dist_b - dist_a - d
            return True
        
    ans = True
    for _ in range(M):
        L,R,D = map(int,input().split())
        if not (unite(L-1,R-1,D,root,depth,dist)):
            ans = False
            break
    print("Yes" if ans else "No")