## CCO '21 P3 - Through Another Maze Darkly

View as PDF

Points: 25 (partial)
Time limit: 8.0s
Memory limit: 1G

Author:
Problem types

There is a maze that is formed by connecting rooms via corridors. The rooms are numbered to 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 queries to investigate this strategy. For each query, you are given an integer and you start at room 1. Determine the final room after traversing exactly corridors. All laser pointers will reset to their original orientation after each query.

#### Input Specification

The first line contains the integers and .

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

The final lines describe a query, with each line containing an integer .

For 4 of the 25 available marks, the th corridor forms a connection between room and room .

For an additional 4 of the 25 available marks, and .

For an additional 12 of the 25 available marks, .

#### Output Specification

Output lines answering the queries in order.

#### Sample Input

5 6
1 2
3 3 1 4
1 2
2 5 2
1 4
1
2
3
4
5
6

#### Sample Output

2
1
2
4
2
3

#### Explanation for Sample Output

This is the initial state of the maze.

The strategy will visit these rooms in order:

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

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

So, what does it mean?

• 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.

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

There is a maze that is formed by connecting rooms via corridors.