CCO '21 P3 - Through Another Maze Darkly - Olympiads Online Judge

CCO '21 P3 - Through Another Maze Darkly

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 8.0s

Memory limit: 1G

Author:

Problem types

Canadian Computing Olympiad: 2021 Day 1, Problem 3

There is a maze that is formed by connecting $N$ ~N~ rooms via $N-1$ ~N-1~ corridors. The rooms are numbered $1$ ~1~ to $N$ ~N~ and each room has the shape of a circle. The corridors have the following constraints:

Each corridor forms a connection between two distinct rooms.
Every pair of rooms is connected by exactly one path of connected corridors.

One difficulty in navigating through this maze is that the lights are all out, so you cannot see where you are. To help with navigation, each room contains a laser pointer that initially points to a corridor. Consider the following strategy:

Rotate the room's laser pointer clockwise until it points to another corridor.
Follow the room's laser pointer and traverse the corridor.
Repeat the previous two steps indefinitely.

You created $Q$ ~Q~ queries to investigate this strategy. For each query, you are given an integer $K$ ~K~ and you start at room 1. Determine the final room after traversing exactly $K$ ~K~ corridors. All laser pointers will reset to their original orientation after each query.

Input Specification

The first line contains the integers $N$ ~N~ and $Q$ ~Q~ $(2 \le N \le 800\,000, 1 \le Q \le 800\,000)$ .

The next $N$ ~N~ lines describe the layout of the maze, with the $i$ ~i~th of these lines describing room $i$ ~i~. Specifically, it contains an integer $k$ ~k~, the number of corridors connecting to room $i$ ~i~, followed by $k$ ~k~ integers, $c_1\ c_2\ \dots\ c_k$ ~c_1\ c_2\ \dots\ c_k~, indicating the rooms that these $k$ ~k~ corridors lead to, in clockwise order. Lastly, room $i$ ~i~'s laser pointer initially points to the corridor leading to room $c_1$ ~c_1~.

The final $Q$ ~Q~ lines describe a query, with each line containing an integer $K$ ~K~ $(1 \le K \le 10^{15})$ ~(1 \le K \le 10^{15})~.

For 4 of the 25 available marks, the $i$ ~i~th corridor forms a connection between room $i$ ~i~ and room $i+1$ ~i+1~.

For an additional 4 of the 25 available marks, $N \le 2\,000$ ~N \le 2\,000~ and $Q \le 2\,000$ ~Q \le 2\,000~.

For an additional 12 of the 25 available marks, $Q = 1$ ~Q = 1~.

Output Specification

Output $Q$ ~Q~ lines answering the queries in order.

Sample Input

Sample Output

Explanation for Sample Output

This is the initial state of the maze.

$\text{[math]}$

The strategy will visit these rooms in order:

$\displaystyle 1, 2, 1, 2, 4, 2, 3, \dots$

Comments

3

Apass_test commented on June 6, 2021, 2:50 a.m.

"For 4 of the 25 available marks, the $i$ ~i~-th corridor forms a connection between room $i$ ~i~ and room $i+1$ ~i+1~." It occurs to me that "the $i$ ~i~-th corridor" does not make much sense. If "the $i$ ~i~-th corridor" is among the corridors of a room, then all those corridors are from that room.

So, what does it mean?

4

BalintR commented on June 6, 2021, 4:08 p.m.

It basically means that there will be a corridor going from room 1 to room 2, a corridor from room 2 to room 3, a corridor from room 3 to room 4 and so on.

3

d commented on June 6, 2021, 4:25 a.m.

There is a maze that is formed by connecting $N$ ~N~ rooms via $N-1$ ~N-1~ corridors.