Submission #66973660

Source Code Expand

def solve(n, m, edges, q, xxx):
    leaders = [i for i in range(n)]
    groups = [{i} for i in range(n)]
    links = [{i} for i in range(n)]

    edges = [(u - 1, v - 1) for u, v in edges]
    for u, v in edges:
        links[u].add(v)
        links[v].add(u)

    tmp = m
    ans = []
    for x in xxx:
        u, v = edges[x - 1]
        gu = groups[u]
        gv = groups[v]
        if gu is gv:
            ans.append(tmp)
            continue
        lgu = len(gu)
        lgv = len(gv)
        if lgu < lgv:
            u, v = v, u
            gu, gv = gv, gu
        gu.update(gv)

        tmp -= 1
        lu = links[u]
        lv = links[v]
        for w in lv:
            rw = leaders[w]
            if rw in gu:
                continue
            if rw in lu:
                tmp -= 1
            else:
                lu.add(rw)
                links[w].remove(v)
                links[w].add(u)
        ans.append(tmp)

        for i in gv:
            leaders[i] = u
            groups[i] = gu
            links[i] = lu

    return ans


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
q = int(input())
xxx = list(map(int, input().split()))
ans = solve(n, m, edges, q, xxx)
print('\n'.join(map(str, ans)))

Submission Info

Submission Time
Task F - Contraction
User ikatakos
Language Python (PyPy 3.10-v7.3.12)
Score 0
Code Size 1324 Byte
Status RE
Exec Time 983 ms
Memory 360560 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 525
Status
AC × 1
AC × 19
WA × 3
RE × 23
Set Name Test Cases
Sample example_00.txt
All example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt
Case Name Status Exec Time Memory
example_00.txt AC 54 ms 76520 KiB
hand_00.txt AC 931 ms 350424 KiB
hand_01.txt AC 916 ms 352300 KiB
hand_02.txt AC 983 ms 360560 KiB
hand_03.txt AC 503 ms 330168 KiB
hand_04.txt AC 267 ms 167648 KiB
hand_05.txt AC 99 ms 150456 KiB
hand_06.txt AC 583 ms 351532 KiB
hand_07.txt AC 213 ms 263684 KiB
hand_08.txt AC 448 ms 309560 KiB
hand_09.txt RE 501 ms 288832 KiB
hand_10.txt RE 518 ms 303060 KiB
hand_11.txt RE 538 ms 298712 KiB
hand_12.txt AC 544 ms 260740 KiB
hand_13.txt WA 398 ms 202680 KiB
random_00.txt AC 274 ms 156104 KiB
random_01.txt RE 461 ms 257828 KiB
random_02.txt AC 566 ms 241356 KiB
random_03.txt WA 708 ms 318596 KiB
random_04.txt RE 436 ms 224888 KiB
random_05.txt RE 444 ms 255288 KiB
random_06.txt RE 275 ms 157236 KiB
random_07.txt RE 499 ms 288952 KiB
random_08.txt AC 502 ms 218772 KiB
random_09.txt WA 709 ms 324648 KiB
random_10.txt AC 781 ms 289184 KiB
random_11.txt RE 445 ms 235732 KiB
random_12.txt AC 265 ms 149260 KiB
random_13.txt RE 462 ms 266836 KiB
random_14.txt RE 474 ms 240264 KiB
random_15.txt RE 735 ms 312184 KiB
random_16.txt RE 435 ms 215592 KiB
random_17.txt RE 433 ms 230244 KiB
random_18.txt RE 293 ms 162856 KiB
random_19.txt RE 488 ms 289592 KiB
random_20.txt RE 471 ms 231120 KiB
random_21.txt AC 766 ms 324712 KiB
random_22.txt RE 489 ms 273556 KiB
random_23.txt AC 510 ms 221100 KiB
random_24.txt RE 283 ms 157648 KiB
random_25.txt RE 462 ms 263932 KiB
random_26.txt RE 419 ms 220180 KiB
random_27.txt AC 763 ms 324132 KiB
random_28.txt RE 511 ms 288444 KiB
random_29.txt RE 407 ms 209196 KiB