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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def weight(x):
        root(x)
        return d[x]
    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    d = [0 for i in range(n)]
    for i in range(m):
        x,y,w = LI()
        x -= 1
        y -= 1
        if same(x,y):
            if d[y]-d[x] != w:
                print("No")
                quit()
        else:
            unite(x,y,w)
    print("Yes")
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def unite(x,y,w):
        w += d[x]
        w -= d[y]
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    d = [0 for i in range(n)]
    for i in range(m):
        x,y,w = LI()
        x -= 1
        y -= 1
        if same(x,y):
            if d[y]-d[x] != w:
                print("No")
                quit()
        else:
            unite(x,y,w)
    print("Yes")
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]
    def same(x,y):
        return root(x) == root(y)
    def unite(x,y,w):
        rx = root(x)
        ry = root(y)
        if rank[rx] < rank[ry]:
            par[rx] = y
            d[x] = d[y]-w
        else:
            par[ry] = rx
            d[y] = d[x]+w
            if rank[rx] == rank[ry]:
                rank[rx] += 1

    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    d = [0 for i in range(n)]
    for i in range(m):
        x,y,w = LI()
        x -= 1
        y -= 1
        if same(x,y):
            if d[y]-d[x] != w:
                print("No")
                quit()
        else:
            unite(x,y,w)
    print("Yes")
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
class WeightenedUnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size
        self.__diff_weight = [0] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        self.__diff_weight[u] += self.__diff_weight[self.__root[u]]
        self.__root[u] = self.find(self.__root[u])
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int, w: int):
        w += self.weight(u)
        w -= self.weight(v)

        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x
            w = -w

        self.__root[x] += self.__root[y]
        self.__root[y] = x

        self.__diff_weight[y] = w

    def weight(self, u: int)->int:
        self.find(u)
        return self.__diff_weight[u]

    def diff_weight(self, u: int, v: int)->int:
        return self.weight(v) - self.weight(u)


def people_on_a_line(N: int, M: int, queries: list)->bool:
    uf = WeightenedUnionFind(N)
    for l, r, d in queries:
        if uf.same(l-1, r-1):
            if d != uf.diff_weight(l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1, d)

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
class WeightenedUnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size
        self.__diff_weight = [0] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        self.__diff_weight[u] += self.__diff_weight[self.__root[u]]
        self.__root[u] = self.find(self.__root[u])
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int, w: int):
        w += self.weight(u)
        w -= self.weight(v)

        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x
            w = -w

        self.__root[x] += self.__root[y]
        self.__root[y] = x

        self.__diff_weight[y] = w

    def weight(self, u: int)->int:
        return self.__diff_weight[u]

    def diff_weight(self, u: int, v: int)->int:
        return self.weight(v) - self.weight(u)


def people_on_a_line(N: int, M: int, queries: list)->bool:
    uf = WeightenedUnionFind(N)
    for l, r, d in queries:
        if uf.same(l-1, r-1):
            if d != uf.diff_weight(l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1, d)

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
import heapq

INF = float('inf')


class WeightenedUnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size
        self.__diff_weight = [0] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        self.__diff_weight[u] += self.__diff_weight[self.__root[u]]
        self.__root[u] = self.find(self.__root[u])
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int, w: int):
        w += self.weight(u)
        w -= self.weight(v)

        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x
            w = -w

        self.__root[x] += self.__root[y]
        self.__root[y] = x

        self.__diff_weight[y] = w

    def weight(self, u: int)->int:
        return self.__diff_weight[u]

    def diff_weight(self, u: int, v: int)->int:
        return self.weight(v) - self.weight(u)

    def print(self):
        print(self.__root)


class PriorityQueue:
    def __init__(self):
        self.__queue = []
        self.__count = 0

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__queue, v)

    def dequeue(self):
        self.__count -= 1
        return heapq.heappop(self.__queue)

    def is_empty(self)->bool:
        return self.__count == 0


def dijkstra(V: int, E: list, s: int, t: int)->int:
    '''dijkstra 法を使って u -> v の距離を求める。
    :param V: 頂点数
    :param E: 辺の集合
    :param s: 始点
    :param t: 終点
    :return: 距離
    '''
    d = [INF] * (V)
    d[s] = 0

    q = PriorityQueue()
    for v in range(V):
        q.enqueue((d[v], v))

    while not q.is_empty():
        _, u = q.dequeue()
        for v, c in E[u]:
            if d[u] + c < d[v]:
                d[v] = d[u] + c
                q.enqueue((d[v], v))

    return d[t]


def people_on_a_line(N: int, M: int, queries: list)->bool:
    # E = [[] for _ in range(N)]
    uf = WeightenedUnionFind(N)
    for l, r, d in queries:
        if uf.same(l-1, r-1):
            # if d != dijkstra(N, E, l-1, r-1):
            #     return False
            if d != uf.diff_weight(l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1, d)

            # E[l-1].append((r-1, d))
            # E[r-1].append((l-1, -d))

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
import heapq

INF = float('inf')


class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        self.__root[u] = self.find(self.__root[u])
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int):
        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x

        self.__root[x] += self.__root[y]
        self.__root[y] = x

    def print(self):
        print(self.__root)


class PriorityQueue:
    def __init__(self):
        self.__queue = []
        self.__count = 0

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__queue, v)

    def dequeue(self):
        self.__count -= 1
        return heapq.heappop(self.__queue)

    def is_empty(self)->bool:
        return self.__count == 0


def dijkstra(V: int, E: list, s: int, t: int)->int:
    '''dijkstra 法を使って u -> v の距離を求める。
    :param V: 頂点数
    :param E: 辺の集合
    :param s: 始点
    :param t: 終点
    :return: 距離
    '''
    d = [INF] * (V)
    d[s] = 0

    q = PriorityQueue()
    for v in range(V):
        q.enqueue((d[v], v))

    while not q.is_empty():
        _, u = q.dequeue()
        for v, c in E[u]:
            if d[u] + c < d[v]:
                d[v] = d[u] + c
                q.enqueue((d[v], v))

    return d[t]


def people_on_a_line(N: int, M: int, queries: list)->bool:
    E = [[] for _ in range(N)]
    uf = UnionFind(N)
    for l, r, d in sorted(queries, key=lambda x: x[2]):
        if uf.same(l-1, r-1):
            if d != dijkstra(N, E, l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1)
            E[l-1].append((r-1, d))
            # E[r-1].append((l-1, d))

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
import heapq

INF = float('inf')


class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        self.__root[u] = self.find(self.__root[u])
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int):
        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x

        self.__root[x] += self.__root[y]
        self.__root[y] = x

    def print(self):
        print(self.__root)


class PriorityQueue:
    def __init__(self):
        self.__queue = []
        self.__count = 0

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__queue, v)

    def dequeue(self):
        self.__count -= 1
        return heapq.heappop(self.__queue)

    def is_empty(self)->bool:
        return self.__count == 0


def dijkstra(V: int, E: list, s: int, t: int)->int:
    '''dijkstra 法を使って u -> v の距離を求める。
    :param V: 頂点数
    :param E: 辺の集合
    :param s: 始点
    :param t: 終点
    :return: 距離
    '''
    d = [INF] * (V)
    d[s] = 0

    q = PriorityQueue()
    for v in range(V):
        q.enqueue((d[v], v))

    while not q.is_empty():
        _, u = q.dequeue()
        for v, c in E[u]:
            if d[u] + c < d[v]:
                d[v] = d[u] + c
                q.enqueue((d[v], v))

    return d[t]


def people_on_a_line(N: int, M: int, queries: list)->bool:
    E = [[] for _ in range(N)]
    uf = UnionFind(N)
    for l, r, d in sorted(queries, key=lambda x: x[2]):
        if uf.same(l-1, r-1):
            if d != dijkstra(N, E, l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1)
            E[l-1].append((r-1, d))
            E[r-1].append((l-1, d))

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
import heapq

INF = float('inf')


class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, u: int)->int:
        if self.__root[u] < 0:
            return u
        self.__root[u] = self.find(self.__root[u])
        return self.__root[u]

    def same(self, u: int, v: int)->bool:
        return self.find(u) == self.find(v)

    def unite(self, u: int, v: int):
        x, y = self.find(u), self.find(v)

        if x == y:
            return

        if self.__root[y] < self.__root[x]:
            x, y = y, x

        self.__root[x] += self.__root[y]
        self.__root[y] = x

    def print(self):
        print(self.__root)


class PriorityQueue:
    def __init__(self):
        self.__queue = []
        self.__count = 0

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__queue, v)

    def dequeue(self):
        self.__count -= 1
        return heapq.heappop(self.__queue)

    def is_empty(self)->bool:
        return self.__count == 0


def dijkstra(V: int, E: list, s: int, t: int)->int:
    '''dijkstra 法を使って u -> v の距離を求める。
    :param V: 頂点数
    :param E: 辺の集合
    :param s: 始点
    :param t: 終点
    :return: 距離
    '''
    d = [INF] * (V)
    d[s] = 0

    q = PriorityQueue()
    for v in range(V):
        q.enqueue((d[v], v))

    while not q.is_empty():
        _, u = q.dequeue()
        for v, c in E[u]:
            if d[u] + c < d[v]:
                d[v] = d[u] + c
                q.enqueue((d[v], v))

    return d[t]


def people_on_a_line(N: int, M: int, queries: list)->bool:
    E = [[] for _ in range(N)]
    uf = UnionFind(N)
    for l, r, d in queries:
        if uf.same(l-1, r-1):
            if d != dijkstra(N, E, l-1, r-1):
                return False
        else:
            uf.unite(l-1, r-1)
            E[l-1].append((r-1, d))
            E[r-1].append((l-1, d))

    return True


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]
    yes = people_on_a_line(N, M, queries)
    print('Yes' if yes else 'No')

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

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

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

def main():
    max_v, max_e = map(int, input().split())
    uf = WeightedUnionFind(max_v)
    k = []
    s = 0
    for i in range(max_e):
        a,b,w= map(int, input().split())
        if a not in k:
            k.append(a)
        if b not in k:
            k.append(b)
        if a in k and b in k:
            uf.diff(a,b) == w
            s =1
        else:uf.union(a,b,w)
    if s == 0:
        print("Yes")
    else:
        print("No")

 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

D = [list(map(int, input().split())) for i in range(m)]
for i in range(m) :
    if D[i][0] > D[i][1] :
        D[i][0], D[i][1] = D[i][1], D[i][0]
        D[i][2] = -D[i][2]
D.sort(key=lambda x:x[1])
D.sort()

#print(D)
P = ["n" for i in range(n+1)]
P[0] = 0
no = 0

for i in range(m) :
    #print(P)
    if P[D[i][0]] == "n" :
        P[D[i][0]] = 0
        P[D[i][1]] = D[i][2]
    elif P[D[i][1]] == "n" :
        P[D[i][1]] = P[D[i][0]] + D[i][2]
    else :
        if P[D[i][1]] - P[D[i][0]] != D[i][2] :
            #print("{} {} {}".format(P[D[i][1]],P[D[i][0]],P[D[i][2]]))
            no = 1

if no == 1 :
    print("No")
else :
    print("Yes")

Submission status: Wrong Answer

Solution code:
def prepare(n):
    global nodes,diff_weight
    # ノードは-1で初期化, Nは頂点数
    nodes = [-1]*n
    # 差分重みは0で初期化, Nは頂点数
    diff_weight = [0]*n

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    # xの重みを知りたいので経路圧縮
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# x,yの根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xの木の高さを返す
def rank(x):
    return -nodes[root(x)]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 再帰的に根を調べる
        root_x = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        # xを根に直接繋ぎ直す
        nodes[x] = root_x
        return root_x

def unite(x,y,w):
    rx = root(x); ry = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if rx == ry:
        return
    rank_x = rank(rx); rank_y = rank(ry)
    # xの方が木が高いことを想定しているので下の場合はx,yをスワップ,wを-wに
    if rank_x < rank_y:
        x,y = y,x; w = -w
    # 木の高さが同じ場合は繋いだ後の高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[rx] -= 1
    # 低い木の根を高い木の根に繋ぎ直す
    nodes[ry] = rx
    # 低い木の根の差分重みを設定
    diff_weight[ry] = w + weight(x) - weight(y)

N,M = map(int,input().split())
prepare(N)
ans = "Yes"
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
def prepare(n):
    global nodes,diff_weight
    # ノードは-1で初期化, Nは頂点数
    nodes = [-1]*n
    # 差分重みは0で初期化, Nは頂点数
    diff_weight = [0]*n

# 差分重みの累積和をとることでxの重みが分かる
def weight(x):
    # xの重みを知りたいので経路圧縮
    root(x)
    return diff_weight[x]

# xからyへの重み
def diff(x,y):
    return weight(y) - weight(x)

# x,yの根が同じ->True
def same(x,y):
    return root(x) == root(y)

# xの木の高さを返す
def rank(x):
    return -nodes[x]

def root(x):
    # ノードが負 <=> xは根
    if nodes[x] < 0:
        return x
    else:
        # 再帰的に根を調べる
        root_x = root(nodes[x])
        # 根に近いものから親の重みを足す. これがxを根に直接繋いだ時の重みになる
        diff_weight[x] += diff_weight[nodes[x]]
        # xを根に直接繋ぎ直す
        nodes[x] = root_x
        return root_x

def unite(x,y,w):
    rx = root(x); ry = root(y)
    # 根が同じならreturn (自己ループを考慮)
    if rx == ry:
        return
    rank_x = rank(rx); rank_y = rank(ry)
    # xの方が木が高いことを想定しているのでx,yをスワップ,wを-wに
    if rank_x < rank_y:
        x,y = y,x; w = -w
    # 木の高さが同じ場合は繋いだ後の高さが1だけ高くなる
    if rank_x == rank_y:
        nodes[rx] -= 1
    # 低い木の根を高い木の根に繋ぎ直す
    nodes[ry] = rx
    # 低い木の根の差分重みを設定
    diff_weight[y] = w + weight(x) - weight(y)

N,M = map(int,input().split())
prepare(N)
ans = "Yes"
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return nodes[x]

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[root_y] = root_x
        diff_weight[root_y] = w + weight(x) - weight(y)
        if rank[root_x] == rank[root_y]:
            rank[root_x] += 1
    else:
        nodes[root_x] = root_y
        diff_weight[root_x] = -w + weight(y) - weight(x)

def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R):
        if diff(L,R) != D:
            ans = "No"
            break
    else:
        unite(L,R,D)

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[root_y] = w + weight(x) - weight(y)
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[root_x] = -w + weight(y) - weight(x)

def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R) is False:
        unite(L,R,D)
    elif diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return nodes[x]

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    w += weight(x); w -= weight(y)
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w

def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R):
        if diff(L,R) != D:
            ans = "No"
            break
    else:
        unite(L,R,D)

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    w += weight(x); w -= weight(y)
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w

def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R):
        if diff(L,R) != D:
            ans = "No"
            break
    else:
        unite(L,R,D)

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    w += weight(x); w -= weight(y)
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return root_x

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    root_x = root(x); root_y = root(y)
    if root_x == root_y:
        return
    if rank[root_x] >= rank[root_y]:
        nodes[y] = root_x
        diff_weight[y] = w + weight(x) - weight(y)
        if rank[root_x] == rank[root_y]:
            rank[x] += 1
    else:
        nodes[x] = root_y
        diff_weight[x] = -w + weight(x) - weight(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    unite(L,R,D)
    if diff(L,R) != D:
        ans = "No"
        break

print(ans)