結果

問題 No.2325 Skill Tree
ユーザー yu7400kiyu7400ki
提出日時 2023-05-28 15:28:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,100 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 87,124 KB
実行使用メモリ 127,752 KB
最終ジャッジ日時 2023-08-27 12:14:55
合計ジャッジ時間 28,898 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
71,648 KB
testcase_01 AC 93 ms
71,820 KB
testcase_02 WA -
testcase_03 AC 94 ms
71,768 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 388 ms
94,696 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 521 ms
99,636 KB
testcase_12 AC 819 ms
124,828 KB
testcase_13 AC 787 ms
124,892 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 795 ms
124,712 KB
testcase_17 AC 800 ms
124,924 KB
testcase_18 AC 795 ms
124,940 KB
testcase_19 AC 811 ms
124,900 KB
testcase_20 WA -
testcase_21 AC 803 ms
124,800 KB
testcase_22 AC 761 ms
124,896 KB
testcase_23 WA -
testcase_24 AC 740 ms
124,692 KB
testcase_25 AC 758 ms
124,704 KB
testcase_26 AC 753 ms
124,964 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 857 ms
126,444 KB
testcase_33 AC 871 ms
126,472 KB
testcase_34 AC 888 ms
126,404 KB
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

N = int(input())
L = []
A = []
for _ in range(N - 1):
    l, a = map(int, input().split())
    L.append(l)
    A.append(a)
A = [(a, i + 2) for i, a in enumerate(A)]
A_dict = defaultdict(list)
A_dict[1].append(1)
L_dict = defaultdict(lambda: -1)
L_dict[1] = 1
for a, i in A:
    l = L[i - 2]
    if L_dict[a] == -1:
        continue
    if L_dict[a] < l:
        A_dict[l].append(i)
        L_dict[i] = l
    else:
        A_dict[L_dict[a]].append(i)
        L_dict[i] = L_dict[a]

acc = {}
prev = 1
acc[prev] = 1
for i, v in A_dict.items():
    if i == prev: continue
    acc[i] = acc[prev] + len(v)
    prev = i
acc_keys = sorted(acc.keys())

Q = int(input())
for _ in range(Q):
    query = tuple(map(int, input().split()))
    if query[0] == 1:
        x = query[1]
        ok = -1
        ng = len(acc_keys)
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if acc_keys[mid] <= x:
                ok = mid
            else:
                ng = mid
        print(acc[acc_keys[ok]])
    else:
        y = query[1]
        print(L_dict[y])
0