Submission #3955770


Source Code Expand

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


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


if __name__ == "__main__":
    import sys
    N, Q = map(int, input().split())
    nodes = [-1]*N
    result = []
    append = result.append

    for p, a, b in (map(int, l.split()) for l in sys.stdin):
        if not p:
            unite(nodes, a, b)
        else:
            append("Yes" if get_root(nodes, a) == get_root(nodes, 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 882 Byte
Status
Exec Time 430 ms
Memory 9720 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 222 ms 6856 KB
subtask_01_02.txt 20 ms 3828 KB
subtask_01_03.txt 351 ms 8924 KB
subtask_01_04.txt 360 ms 9588 KB
subtask_01_05.txt 43 ms 3760 KB
subtask_01_06.txt 46 ms 4760 KB
subtask_01_07.txt 354 ms 8820 KB
subtask_01_08.txt 377 ms 9592 KB
subtask_01_09.txt 18 ms 3064 KB
subtask_01_10.txt 19 ms 3828 KB
subtask_01_11.txt 355 ms 8856 KB
subtask_01_12.txt 355 ms 9588 KB
subtask_01_13.txt 288 ms 7716 KB
subtask_01_14.txt 20 ms 3956 KB
subtask_01_15.txt 363 ms 8820 KB
subtask_01_16.txt 371 ms 9720 KB
subtask_01_17.txt 428 ms 7028 KB
subtask_01_18.txt 430 ms 7004 KB