a554. [模板]倍增表 - 彰化精誠中學

內容

你正在玩一個由 $n$ 顆行星組成的遊戲。每顆行星都有一個傳送門，可以傳送到另一顆行星（或傳送到自己）。
你的任務是處理 $q$ 次查詢，每次查詢的形式為：當你從行星 $x$ 出發並經過 $k$ 次傳送後，將會到達哪顆行星？

$1 \le n, q \le 2 \cdot 10^5$
$1 \le t_i \le n$
$1 \le x \le n$
$0 \le k \le 10^9$

輸入說明

第一行輸入有兩個整數 $n$ 和 $q$：行星的數量和查詢的數量。行星編號為 $1$, $2$, …, $n$。
第二行有 $n$ 個整數 $t_1$, $t_2$, …, $t_n$：每顆行星的傳送門目的地。可能存在 $t_i = i$ 的情況。
最後，接下來有 $q$ 行描述查詢。每行有兩個整數 $x$ 和 $k$：表示您從行星 $x$ 出發並經過 $k$ 次傳送。

輸出說明

輸出每個查詢的答案。

範例輸入 #1

範例輸出 #1

1
2
4

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (11%): 1.0s , <1K
公開測資點#1 (11%): 1.0s , <1K
公開測資點#2 (11%): 1.0s , <1K
公開測資點#3 (11%): 1.0s , <10M
公開測資點#4 (11%): 1.0s , <10M
公開測資點#5 (11%): 1.0s , <10M
公開測資點#6 (11%): 1.0s , <10M
公開測資點#7 (11%): 1.0s , <1K
公開測資點#8 (12%): 1.0s , <1K

提示：

IO優化

標籤:

倍增表圖論

出處:

cses [管理者：

haha (大學長)

]

編號	身分	題目	主題	人氣	發表日期
140	211096@stu.c... (唐狗針)	a554	如果TLE	39	2024-11-16 20:59