結果

問題 No.2325 Skill Tree
コンテスト
ユーザー yu7400ki
提出日時 2023-05-28 15:28:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,100 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 576 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 136,716 KB
最終ジャッジ日時 2024-12-27 06:53:50
合計ジャッジ時間 27,095 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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