結果

問題 No.2325 Skill Tree
コンテスト
ユーザー koheijkt
提出日時 2026-01-14 23:45:14
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 633 ms / 3,000 ms
コード長 1,176 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 337 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 115,532 KB
最終ジャッジ日時 2026-01-14 23:45:39
合計ジャッジ時間 22,637 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = 1e18
from bisect import bisect_left, bisect_right
from collections import deque

def cnt_ika(li, x): # x 以下の要素数
    return bisect_right(li, x)

N = int(input())
G = [list() for _ in range(N + 1)]
required_level = [INF] * (N + 1)
required_level[1] = 0
for i in range(2, N + 1):
    l, a = map(int, input().split())
    required_level[i] = l
    G[a].append(i)


# 頂点1からBFS
que = deque()
que.append(1)
visited = [False]*(N + 1)
visited[1] = True
while que:
    pos = que.popleft()
    for nex in G[pos]:
        visited[nex] = True
        required_level[nex] = max(required_level[nex], required_level[pos])
        que.append(nex)

waza_available = [] # 実際に覚えられる技だけ入れる
for i in range(1, N + 1):
    if visited[i]:
        waza_available.append(required_level[i])
waza_available.sort()

Q = int(input())
ansl = []
for i in range(Q):
    p, q = map(int, input().split())
    if p == 1:
        #required_level から x 以下の個数
        ans = cnt_ika(waza_available, q)
    else:
        if visited[q]:
            ans = required_level[q]
        else:
            ans = -1
    ansl.append(ans)

print(*ansl, sep='\n')
0