結果

問題 No.2325 Skill Tree
ユーザー konchakoncha
提出日時 2023-05-28 14:27:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 796 ms / 3,000 ms
コード長 1,007 bytes
コンパイル時間 891 ms
コンパイル使用メモリ 87,288 KB
実行使用メモリ 146,024 KB
最終ジャッジ日時 2023-08-27 09:51:23
合計ジャッジ時間 24,940 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 98 ms
71,416 KB
testcase_01 AC 98 ms
71,420 KB
testcase_02 AC 98 ms
71,484 KB
testcase_03 AC 97 ms
71,396 KB
testcase_04 AC 98 ms
71,328 KB
testcase_05 AC 99 ms
71,460 KB
testcase_06 AC 98 ms
71,472 KB
testcase_07 AC 330 ms
98,056 KB
testcase_08 AC 339 ms
103,476 KB
testcase_09 AC 365 ms
105,212 KB
testcase_10 AC 385 ms
115,880 KB
testcase_11 AC 397 ms
113,712 KB
testcase_12 AC 614 ms
145,844 KB
testcase_13 AC 602 ms
145,872 KB
testcase_14 AC 609 ms
145,636 KB
testcase_15 AC 609 ms
145,628 KB
testcase_16 AC 613 ms
145,780 KB
testcase_17 AC 582 ms
145,564 KB
testcase_18 AC 582 ms
145,708 KB
testcase_19 AC 583 ms
145,532 KB
testcase_20 AC 580 ms
145,568 KB
testcase_21 AC 579 ms
145,788 KB
testcase_22 AC 604 ms
145,660 KB
testcase_23 AC 592 ms
145,848 KB
testcase_24 AC 597 ms
145,588 KB
testcase_25 AC 592 ms
145,764 KB
testcase_26 AC 586 ms
145,872 KB
testcase_27 AC 771 ms
146,024 KB
testcase_28 AC 773 ms
144,860 KB
testcase_29 AC 768 ms
144,432 KB
testcase_30 AC 773 ms
144,904 KB
testcase_31 AC 796 ms
145,732 KB
testcase_32 AC 729 ms
145,928 KB
testcase_33 AC 741 ms
145,816 KB
testcase_34 AC 734 ms
145,624 KB
testcase_35 AC 748 ms
145,180 KB
testcase_36 AC 742 ms
145,512 KB
testcase_37 AC 755 ms
145,604 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

N = int(input())
skills = [list(map(int, input().split())) for _ in range(N-1)]
Q = int(input())
querys = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for i, skill in enumerate(skills, start=1):
    graph[skill[1]-1].append(i)

skills = [(0, 0)] + skills

INF = 10**18
levels = [0] + [INF] * (N-1)
queue = deque([(0, 0)])
visited = [False] * (N+1)
visited[0] = False

while queue:
    now, prev = queue.popleft()
    if visited[now]:
        continue
    visited[now] = True
    levels[now] = max(skills[now][0], levels[prev])

    for u in graph[now]:
        queue.append((u, now))

s_levels = [1] + sorted(levels)

for q, l in querys:
    if q == 1:
        ok = 0
        ng = N+1
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if s_levels[mid] <= l:
                ok = mid
            else:
                ng = mid
        print(ok)
    if q == 2:
        print(levels[l-1] if levels[l-1] != INF else -1)
0