RiseOJ – 무한한 모험

설명

*참고: 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.*

베시는 $$N$$ ( $1\leq N \leq 10^5$ )개의 도시가 있는 땅에서 무한한 모험을 계획하고 있다. 각 도시 $$i$$ 에는 포털이 하나 있고, 순환 시간 $$T_i$$ 가 정해져 있다. 모든 $$T_i$$ 는 $$2$$ 의 거듭제곱이고, $T_1 + \cdots + T_N \leq 10^5$ 이다. $$t$$ 일에 도시 $$i$$ 의 포털에 들어가면, 즉시 도시 $c_{i, t\bmod{T_i}}$ 의 포털로 나오게 된다.

베시는 여행에 대한 $$Q$$ ( $1\leq Q \leq 5\cdot 10^4$ )개의 계획을 가지고 있으며, 각 계획은 튜플 $(v, t, \Delta)$ 로 이루어져 있다. 각 계획에서 베시는 $$t$$ 일에 도시 $$v$$ 에서 출발한다. 그 후 다음 행동을 $\Delta$ 번 반복한다: 현재 도시의 포털을 통과한 뒤, 하루를 기다린다. 각 계획에 대해, 베시가 최종적으로 어느 도시에 도착하게 되는지 알고 싶다.

문제 제공: Brandon Wang

제약

배점

입력 3: $\Delta_j \leq 2\cdot 10^2$ .
입력 4-5: $N, \sum T_j\leq 2\cdot 10^3$ .
입력 6-8: $N, \sum T_j\leq 10^4$ .
입력 9-18: 추가 제약 없음.

문제 제공: Brandon Wang

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$N$$ (노드의 수)과 $$Q$$ (쿼리의 수)가 주어진다.

둘째 줄에 공백으로 구분된 $$N$$ 개의 정수 $T_1, T_2, \ldots, T_N$ 이 주어진다 ( $1\leq T_i$ , $$T_i$$ 는 $$2$$ 의 거듭제곱, $T_1 + \cdots + T_N \leq 10^5$ ).

$i = 1, 2, \ldots, N$ 에 대해, $$i+2$$ 번째 줄에 공백으로 구분된 $$T_i$$ 개의 양의 정수 $c_{i, 0}, \ldots, c_{i, T_i-1}$ 이 주어진다 ( $1\leq c_{i, t} \leq N$ ).

$j = 1, 2, \ldots, Q$ 에 대해, $$j+N+2$$ 번째 줄에 $$j$$ 번째 쿼리를 나타내는 공백으로 구분된 세 양의 정수 $v_j, t_j, \Delta_j$ 가 주어진다 ( $1\leq v_j \leq N$ , $1\leq t_j \leq 10^{18}$ , $1\leq \Delta_j \leq 10^{18}$ ).

출력 형식

$$Q$$ 개의 줄을 출력한다. $$j$$ 번째 줄에는 $$j$$ 번째 쿼리의 답을 출력한다.

예제 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

출력

설명

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

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > February > Platinum

올림피아드 > USACO > 2023-2024 > February > Platinum

태그

JudgeUSACO

무한한 모험

평가 및 의견

풀이 제출