結果

問題 No.2325 Skill Tree
ユーザー koncha
提出日時 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0