34350번 - Theseus 서브태스크다국어언어 제한함수 구현투 스텝

문제

If all the parts of the ship of Theseus are replaced one by one over time, at what point − if any − does it stop being the same ship?

When he's not pondering deeply into the abstract, Theseus slays minotaurs in his spare time. This time however, he must first pass through a dark and twisted labyrinth. Since this is no easy feat, he asks the help of Ariadne to guide him. The labyrinth can be seen as a connected undirected graph with $n$ nodes (labelled from 1ドル$ to $n$) and $m$ edges, with a special node $t,ドル where the Minotaur sits.

Theseus cannot see the graph at all, but Ariadne can. She and Theseus will devise a strategy so that he can safely reach the node where the Minotaur is: she will put a label with either 0ドル$ or 1ドル$ on each of the m edges. After this, Theseus will enter the labyrinth through a node $s$ that Ariadne doesn't know beforehand.

Since it's very dark, at any moment in time he can only see the index of the node he's in, the indices of neighbouring nodes, and the labels of the adjacent edges. Also, because of the twisted nature of the labyrinth, he can never recall any information regarding previous nodes he has visited.

To reach the Minotaur safely, Theseus must move at most $min + C$ times, where $min$ is the minimum number of edges on the path from $s$ to $t,ドル and $C$ is a constant.

구현 상세

You will have to implement two functions:

std::vector<int> label(int n, std::vector<std::pair<int,int>> edges, int t);

• $n$: the number of nodes
• $edges$: a list of length $m$ describing the edges of the graph
• $t$: the destination node
• This procedure should return a list of labels of length $m$ where the $i$-th element can be either 0ドル$ or 1ドル$ and it represents the label of the $i$-th edge for all 0ドル ≤ i < m$.
• Every edge must be labelled with either 0ドル$ or 1ドル$. Labelling it with a different label will lead to undefined behaviour.
• This procedure is called exactly once for each test case.

int travel(int n, int u, std::vector<std::pair<int,int>> neighbours);

• $n$: the number of nodes in the graph
• $u$: the current node
• $neighbours$: a list of pairs $(v, e)$ denoting that there is an edge between $u$ and $v$ labelled with $e$
• This procedure should return a neighbouring node to move to. If the neighbouring node is $t,ドル the program terminates automatically.
• It is guaranteed that for any call to this function, $u$ will not be equal to the special node $t$.
• A call to this procedure represents a move through the labyrinth. Therefore, for each test case, this procedure can be called as many times as necessary in order to reach the destination node.

Attention! The program should not use global/static variables to communicate between different instances of label or travel. Any attempt to circumvent this would lead to undefined behaviour.

입력

출력

제한

• 1ドル ≤ n ≤ 10,000円$
• 1ドル ≤ m ≤ 50,000円$
• $C = 14$
• The start node $s$ is fixed for each test before calling function label.

서브태스크

힌트

예제

Example 1

Consider we have a graph with 7 nodes and 7 edges (listed below). The start node will be 3 (marked with green) and the destination node is 7 (marked with red). The grader will first call:

label(7, {{1, 6}, {7, 6}, {2, 5}, {3, 2}, {3, 6}, {6, 5}, {6, 4}}, 7)

Let's assume the call to label returns {0, 1, 1, 1, 0, 1, 0}. Then the resulting graph will look like this:

What follows is a possible sequence of calls to travel that will lead to a correct solution:

When the returned value is 7ドル$ (i.e. the destination), the program stops.

샘플 그레이더

The sample grader reads the input in the following format:

• line 1ドル$: $n$ $m$
• line 2ドル$: $s$ $t$
• line 3ドル + i$: $a$ $b$ denoting that there is an edge connecting nodes $a$ and $b$.

First the grader will call label with the corresponding parameters and will label the edges of the graph according to the returned vector.

Then it will call travel with parameters $n,ドル $s$ and the neighbours of $s$. After the first call it will keep making successive calls to travel, with the current node being the one returned by the previous call, until the destination $t$ is reached.

In the end it will print the number of moves your solution made and the nodes it passed in order.

첨부

• sample-grader.cpp theseus.h