Submission #68826180

Source Code Expand

import sys
readline = sys.stdin.readline


def solve_case():
    N = int(readline())
    par = [-1] + [int(x) - 1 for x in readline().split()]

    # depth, subtree size
    dep = [0] * N
    sub = [1] * N
    for v in range(1, N):
        dep[v] = dep[par[v]] + 1
    for v in range(N - 1, 0, -1):
        sub[par[v]] += sub[v]

    ma = 0
    for v in range(N):
        U = N - dep[v] - sub[v]
        odd = dep[v] + 1 + (sub[v] - 1) % 2
        ma = max(ma, odd - U)

    ANS = (N - ma) // 2
    print(ANS)


T = int(readline())
for _ in range(T):
    solve_case()

Submission Info

Submission Time
Task D - Non-Ancestor Matching
User maspy
Language Python (PyPy 3.10-v7.3.12)
Score 600
Code Size 597 Byte
Status AC
Exec Time 126 ms
Memory 136076 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 1
AC × 86
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 02_handmade_00.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt, 02_handmade_07.txt, 02_handmade_08.txt, 02_handmade_09.txt, 02_handmade_10.txt, 02_handmade_11.txt, 02_handmade_12.txt, 02_handmade_13.txt, 02_handmade_14.txt, 02_handmade_15.txt, 02_handmade_16.txt, 02_handmade_17.txt, 02_handmade_18.txt, 02_handmade_19.txt, 02_handmade_20.txt, 02_handmade_21.txt, 02_handmade_22.txt, 02_handmade_23.txt, 02_handmade_24.txt, 02_handmade_25.txt, 02_handmade_26.txt, 02_handmade_27.txt, 02_handmade_28.txt, 02_handmade_29.txt, 02_handmade_30.txt, 02_handmade_31.txt, 02_handmade_32.txt, 02_handmade_33.txt, 02_handmade_34.txt, 02_handmade_35.txt, 02_handmade_36.txt, 02_handmade_37.txt, 02_handmade_38.txt, 02_handmade_39.txt, 02_handmade_40.txt, 02_handmade_41.txt, 02_handmade_42.txt, 02_handmade_43.txt, 02_handmade_44.txt, 03_random_00.txt, 03_random_01.txt, 03_random_02.txt, 03_random_03.txt, 03_random_04.txt, 03_random_05.txt, 03_random_06.txt, 03_random_07.txt, 03_random_08.txt, 03_random_09.txt, 03_random_10.txt, 03_random_11.txt, 03_random_12.txt, 03_random_13.txt, 03_random_14.txt, 03_random_15.txt, 03_random_16.txt, 03_random_17.txt, 03_random_18.txt, 03_random_19.txt, 03_random_20.txt, 03_random_21.txt, 03_random_22.txt, 03_random_23.txt, 03_random_24.txt, 03_random_25.txt, 03_random_26.txt, 04_from_path_subtree_01.txt, 04_from_path_subtree_02.txt, 04_from_path_subtree_03.txt, 04_from_path_subtree_04.txt, 04_from_path_subtree_05.txt, 04_from_path_subtree_06.txt, 04_from_path_subtree_07.txt, 04_from_path_subtree_08.txt, 04_from_path_subtree_09.txt, 04_from_path_subtree_10.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 60 ms 76648 KiB
01_small_00.txt AC 117 ms 84596 KiB
01_small_01.txt AC 121 ms 84492 KiB
01_small_02.txt AC 117 ms 84352 KiB
02_handmade_00.txt AC 105 ms 135984 KiB
02_handmade_01.txt AC 120 ms 128788 KiB
02_handmade_02.txt AC 119 ms 128816 KiB
02_handmade_03.txt AC 120 ms 128584 KiB
02_handmade_04.txt AC 121 ms 128720 KiB
02_handmade_05.txt AC 118 ms 128876 KiB
02_handmade_06.txt AC 117 ms 128636 KiB
02_handmade_07.txt AC 120 ms 129136 KiB
02_handmade_08.txt AC 121 ms 129060 KiB
02_handmade_09.txt AC 119 ms 129076 KiB
02_handmade_10.txt AC 97 ms 83232 KiB
02_handmade_11.txt AC 97 ms 83540 KiB
02_handmade_12.txt AC 96 ms 83312 KiB
02_handmade_13.txt AC 98 ms 83396 KiB
02_handmade_14.txt AC 98 ms 83384 KiB
02_handmade_15.txt AC 96 ms 83316 KiB
02_handmade_16.txt AC 98 ms 83332 KiB
02_handmade_17.txt AC 98 ms 83356 KiB
02_handmade_18.txt AC 117 ms 128900 KiB
02_handmade_19.txt AC 101 ms 83388 KiB
02_handmade_20.txt AC 99 ms 83340 KiB
02_handmade_21.txt AC 98 ms 83508 KiB
02_handmade_22.txt AC 101 ms 83188 KiB
02_handmade_23.txt AC 100 ms 83376 KiB
02_handmade_24.txt AC 101 ms 83416 KiB
02_handmade_25.txt AC 102 ms 83876 KiB
02_handmade_26.txt AC 102 ms 83368 KiB
02_handmade_27.txt AC 102 ms 83524 KiB
02_handmade_28.txt AC 102 ms 83356 KiB
02_handmade_29.txt AC 101 ms 83496 KiB
02_handmade_30.txt AC 98 ms 83144 KiB
02_handmade_31.txt AC 120 ms 128780 KiB
02_handmade_32.txt AC 119 ms 128564 KiB
02_handmade_33.txt AC 118 ms 128808 KiB
02_handmade_34.txt AC 121 ms 128568 KiB
02_handmade_35.txt AC 120 ms 128572 KiB
02_handmade_36.txt AC 119 ms 128936 KiB
02_handmade_37.txt AC 119 ms 128956 KiB
02_handmade_38.txt AC 120 ms 128760 KiB
02_handmade_39.txt AC 124 ms 128912 KiB
02_handmade_40.txt AC 121 ms 128684 KiB
02_handmade_41.txt AC 123 ms 128688 KiB
02_handmade_42.txt AC 121 ms 128728 KiB
02_handmade_43.txt AC 122 ms 128988 KiB
02_handmade_44.txt AC 119 ms 128744 KiB
03_random_00.txt AC 125 ms 129108 KiB
03_random_01.txt AC 126 ms 129292 KiB
03_random_02.txt AC 126 ms 129216 KiB
03_random_03.txt AC 126 ms 129144 KiB
03_random_04.txt AC 124 ms 129108 KiB
03_random_05.txt AC 125 ms 129248 KiB
03_random_06.txt AC 123 ms 128996 KiB
03_random_07.txt AC 121 ms 129228 KiB
03_random_08.txt AC 123 ms 129144 KiB
03_random_09.txt AC 125 ms 129224 KiB
03_random_10.txt AC 103 ms 136008 KiB
03_random_11.txt AC 106 ms 136076 KiB
03_random_12.txt AC 115 ms 134308 KiB
03_random_13.txt AC 113 ms 132776 KiB
03_random_14.txt AC 100 ms 83044 KiB
03_random_15.txt AC 101 ms 83348 KiB
03_random_16.txt AC 100 ms 83080 KiB
03_random_17.txt AC 101 ms 83392 KiB
03_random_18.txt AC 101 ms 83156 KiB
03_random_19.txt AC 117 ms 128908 KiB
03_random_20.txt AC 118 ms 128852 KiB
03_random_21.txt AC 119 ms 128548 KiB
03_random_22.txt AC 119 ms 128480 KiB
03_random_23.txt AC 119 ms 128500 KiB
03_random_24.txt AC 119 ms 128640 KiB
03_random_25.txt AC 119 ms 129040 KiB
03_random_26.txt AC 121 ms 128592 KiB
04_from_path_subtree_01.txt AC 123 ms 128600 KiB
04_from_path_subtree_02.txt AC 125 ms 128984 KiB
04_from_path_subtree_03.txt AC 123 ms 128944 KiB
04_from_path_subtree_04.txt AC 124 ms 128576 KiB
04_from_path_subtree_05.txt AC 123 ms 128920 KiB
04_from_path_subtree_06.txt AC 121 ms 128736 KiB
04_from_path_subtree_07.txt AC 124 ms 128532 KiB
04_from_path_subtree_08.txt AC 122 ms 128768 KiB
04_from_path_subtree_09.txt AC 123 ms 129088 KiB
04_from_path_subtree_10.txt AC 121 ms 128548 KiB