Submission #3955762


Source Code Expand

Copy
class UnionFind(object):
    __slots__ = ["nodes"]

    def __init__(self, n: int):
        self.nodes = [-1]*n

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            bigroot, smallroot = \
                (root_x, root_y) if self.nodes[root_x] < self.nodes[root_y] else (root_y, root_x)
            self.nodes[bigroot] += self.nodes[smallroot]
            self.nodes[smallroot] = bigroot


if __name__ == "__main__":
    import sys
    N, Q = map(int, input().split())
    union_find = UnionFind(N)
    unite, get_root = union_find.unite, union_find.get_root
    result = []
    append = result.append

    for p, a, b in (map(int, l.split()) for l in sys.stdin):
        if not p:
            unite(a, b)
        else:
            append("Yes" if get_root(a) == get_root(b) else "No")

    print(*result, sep="\n")

Submission Info

Submission Time
Task B - Union Find
User htkb
Language Python3 (3.4.3)
Score 100
Code Size 1139 Byte
Status
Exec Time 515 ms
Memory 9716 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01.txt
All 100 / 100 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt
Case Name Status Exec Time Memory
00_sample_01.txt 18 ms 3064 KB
subtask_01_01.txt 224 ms 6856 KB
subtask_01_02.txt 20 ms 3828 KB
subtask_01_03.txt 344 ms 8936 KB
subtask_01_04.txt 379 ms 9716 KB
subtask_01_05.txt 42 ms 3760 KB
subtask_01_06.txt 47 ms 4748 KB
subtask_01_07.txt 365 ms 8836 KB
subtask_01_08.txt 366 ms 9592 KB
subtask_01_09.txt 18 ms 3064 KB
subtask_01_10.txt 20 ms 3828 KB
subtask_01_11.txt 348 ms 8856 KB
subtask_01_12.txt 371 ms 9588 KB
subtask_01_13.txt 300 ms 7716 KB
subtask_01_14.txt 21 ms 3956 KB
subtask_01_15.txt 363 ms 8836 KB
subtask_01_16.txt 395 ms 9588 KB
subtask_01_17.txt 512 ms 7028 KB
subtask_01_18.txt 515 ms 7036 KB