結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
from collections import dequeN = 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)] + skillsINF = 10**18levels = [0] + [INF] * (N-1)queue = deque([(0, 0)])visited = [False] * (N+1)visited[0] = Falsewhile queue:now, prev = queue.popleft()if visited[now]:continuevisited[now] = Truelevels[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 = 0ng = N+1while abs(ok-ng) > 1:mid = (ok+ng)//2if s_levels[mid] <= l:ok = midelse:ng = midprint(ok)if q == 2:print(levels[l-1] if levels[l-1] != INF else -1)