#PU1406. USACO 2024 February Contest, Platinum — Problem 3. Infinite Adventure

    ID: 1423 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb24来源:usaco.orgscoring:equal_test_cases离散化

USACO 2024 February Contest, Platinum — Problem 3. Infinite Adventure

USACO 2024 February Contest, Platinum — Problem 3. Infinite Adventure

题目描述

Note: The memory limit for this problem is 512MB, twice the default. Bessie is planning an infinite adventure in a land with NN (1≤N≤1051\leq N \leq 10^5) cities. In each city ii, there is a portal, as well as a cycling time TiT_i. All TiT_i's are powers of 22, and T1+⋯+TN≤105T_1 + \cdots + T_N \leq 10^5. If you enter city ii's portal on day tt, then you instantly exit the portal in city ci,t mod Tic_{i, t\bmod{T_i}}. Bessie has QQ (1≤Q≤5⋅1041\leq Q \leq 5\cdot 10^4) plans for her trip, each of which consists of a tuple (v,t,Δ)(v, t, \Delta). In each plan, she will start in city vv on day tt. She will then do the following Δ\Delta times: She will follow the portal in her current city, then wait one day. For each of her plans, she wants to know what city she will end up in.

输入格式

The first line contains two space-separated integers: NN, the number of nodes, and QQ, the number of queries. The second line contains NN space-separated integers: T1,T2,…,TNT_1, T_2, \ldots, T_N (1≤Ti1\leq T_i, TiT_i is a power of 22, and T1+⋯+TN≤105T_1 + \cdots + T_N \leq 10^5). For i=1,2,…,Ni = 1, 2, \ldots, N, line i+2i+2 contains TiT_i space-separated positive integers, namely ci,0,…,ci,Ti−1c_{i, 0}, \ldots, c_{i, T_i-1} (1≤ci,t≤N1\leq c_{i, t} \leq N). For j=1,2,…,Qj = 1, 2, \ldots, Q, line j+N+2j+N+2 contains three space-separated positive integers, vj,tj,Δjv_j, t_j, \Delta_j (1≤vj≤N1\leq v_j \leq N, 1≤tj≤10181\leq t_j \leq 10^{18}, and 1≤Δj≤10181\leq \Delta_j \leq 10^{18}) representing the jjth query.

输出格式

Print QQ lines. The jjth line must contain the answer to the jjth query.

数据范围

(见题面原文)

样例

样例 1

5 4
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 3 6
5 3 2
5 3 7
2
2
5
4
Bessie's first three adventures proceed as follows:
In the first adventure, she goes from city $2$ at time $4$ to city $3$ at time $5$, to city $4$ at time $6$, to city $2$ at time $7$.
In the second adventure, she goes from city $3$ at time $3$ to city $4$ at time $4$, to city $2$ at time $5$, to city $4 $ at time $6$, to city $2$ at time $7$, to city $4$ at time $8$, to city $2$ at time $9$.
In the third adventure, she goes from city $5$ at time $3$ to city $5$ at time $4$, to city $5$ at time $5$.

样例 2

5 5
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 2 6
5 3 2
5 3 7
5 3 1000000000000000000
2
3
5
4
2