Infinite Adventure
다이아몬드 V의견: 0
*Note: The memory limit for this problem is 512MB, twice the default.*
Bessie is planning an infinite adventure in a land with \(N\)
(\(1\leq N \leq 10^5\)) cities. In each city \(i\), there is a portal, as well as a
cycling time \(T_i\). All \(T_i\)'s are powers of \(2\), and
\(T_1 + \cdots + T_N \leq 10^5\). If you enter city \(i\)'s portal on day \(t\), then
you instantly exit the portal in city
\(c_{i, t\bmod{T_i}}\).
Bessie has \(Q\) (\(1\leq Q \leq 5\cdot 10^4\)) plans for her trip, each of which
consists of a tuple \((v, t, \Delta)\). In each plan, she will start in city \(v\)
on day \(t\). 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.
Problem credits: Brandon Wang
SCORING
- Input 3: \(\Delta_j \leq 2\cdot 10^2\).
- Inputs 4-5: \(N, \sum T_j\leq 2\cdot 10^3\).
- Inputs 6-8: \(N, \sum T_j\leq 10^4\).
- Inputs 9-18: No additional constraints.
Problem credits: Brandon Wang
The first line contains two space-separated integers: \(N\), the number of nodes,
and \(Q\), the number of queries.
The second line contains \(N\) space-separated integers: \(T_1, T_2, \ldots, T_N\)
(\(1\leq T_i\), \(T_i\) is a power of \(2\), and \(T_1 + \cdots + T_N \leq 10^5\)).
For \(i = 1, 2, \ldots, N\), line \(i+2\) contains \(T_i\) space-separated positive
integers, namely \(c_{i, 0}, \ldots, c_{i, T_i-1}\) (\(1\leq c_{i, t} \leq N\)).
For \(j = 1, 2, \ldots, Q\), line \(j+N+2\) contains three space-separated positive
integers, \(v_j, t_j, \Delta_j\) (\(1\leq v_j \leq N\), \(1\leq t_j \leq 10^{18}\),
and \(1\leq \Delta_j \leq 10^{18}\)) representing the \(j\)th query.
Print \(Q\) lines. The \(j\)th line must contain the answer to the \(j\)th query.
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 72
2
5
4Bessie'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\).
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 10000000000000000002
3
5
4
2riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Platinum
평가 및 의견
Infinite Adventure
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Infinite Adventure