結果

問題 No.2325 Skill Tree
ユーザー konchakoncha
提出日時 2023-05-28 14:27:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 665 ms / 3,000 ms
コード長 1,007 bytes
コンパイル時間 844 ms
コンパイル使用メモリ 81,784 KB
実行使用メモリ 146,004 KB
最終ジャッジ日時 2024-12-27 01:20:22
合計ジャッジ時間 19,834 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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