結果

問題 No.2325 Skill Tree
ユーザー yu7400kiyu7400ki
提出日時 2023-05-28 15:28:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,100 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 137,224 KB
最終ジャッジ日時 2024-06-08 07:50:11
合計ジャッジ時間 23,804 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,248 KB
testcase_01 AC 39 ms
53,888 KB
testcase_02 WA -
testcase_03 AC 39 ms
54,144 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 304 ms
95,544 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 412 ms
99,256 KB
testcase_12 AC 683 ms
116,744 KB
testcase_13 AC 676 ms
117,348 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 660 ms
117,376 KB
testcase_17 AC 655 ms
116,996 KB
testcase_18 AC 658 ms
116,996 KB
testcase_19 AC 658 ms
117,376 KB
testcase_20 WA -
testcase_21 AC 660 ms
117,364 KB
testcase_22 AC 623 ms
116,876 KB
testcase_23 WA -
testcase_24 AC 594 ms
117,384 KB
testcase_25 AC 613 ms
117,132 KB
testcase_26 AC 612 ms
117,508 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 700 ms
136,968 KB
testcase_33 AC 710 ms
135,572 KB
testcase_34 AC 733 ms
135,676 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