結果
問題 |
No.2325 Skill Tree
|
ユーザー |
![]() |
提出日時 | 2025-07-13 21:17:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 846 ms / 3,000 ms |
コード長 | 1,222 bytes |
コンパイル時間 | 281 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 163,668 KB |
最終ジャッジ日時 | 2025-07-13 21:17:35 |
合計ジャッジ時間 | 24,755 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
from bisect import bisect_left, bisect_right from collections import defaultdict def find_interval(a: list, lo: int, hi: int) -> tuple[int, int, int]: """ ソート済みリスト a の要素の lo 以上 hi 以下の個数と区間を返す return: 範囲内の個数, l, r """ assert lo <= hi empty = 0, -1, -1 # 区間なし if not a or lo > a[-1] or hi < a[0]: return empty l = bisect_left(a, lo) r = bisect_right(a, hi) - 1 if l > r: return empty return r-l+1, l, r N = int(input()) skills = [(0, 0)] adj = defaultdict(list) for i in range(N-1): L, A = map(int, input().split()) A -= 1 skills.append((L, A)) adj[A].append(i+1) Q = int(input()) queries = [] for _ in range(Q): qs = list(map(int, input().split())) queries.append(qs) def dfs(si, lv): levels[si] = max(levels[si], lv) for to in adj[si]: dfs(to, max(lv, skills[to][0])) levels = [-1] * N dfs(0, 0) levels_sorted = sorted(levels) for i in range(len(queries)): qs = queries[i] if qs[0] == 1: x = qs[1] cnt, _, _ = find_interval(levels_sorted, 0, x) print(cnt) elif qs[0] == 2: y = qs[1]-1 print(levels[y])