Submission #3955758

Source Code Expand

Copy
class UnionFind(object):
    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 1110 Byte
Status
Exec Time 507 ms
Memory 9588 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 17 ms 3064 KB
subtask_01_01.txt 239 ms 6856 KB
subtask_01_02.txt 19 ms 3828 KB
subtask_01_03.txt 347 ms 8940 KB
subtask_01_04.txt 364 ms 9588 KB
subtask_01_05.txt 42 ms 3760 KB
subtask_01_06.txt 46 ms 4748 KB
subtask_01_07.txt 365 ms 8836 KB
subtask_01_08.txt 359 ms 9588 KB
subtask_01_09.txt 17 ms 3064 KB
subtask_01_10.txt 19 ms 3828 KB
subtask_01_11.txt 345 ms 8856 KB
subtask_01_12.txt 367 ms 9588 KB
subtask_01_13.txt 288 ms 7840 KB
subtask_01_14.txt 20 ms 3956 KB
subtask_01_15.txt 364 ms 8832 KB
subtask_01_16.txt 384 ms 9588 KB
subtask_01_17.txt 498 ms 7028 KB
subtask_01_18.txt 507 ms 7028 KB