| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 91 | 4 | 4 | 5.195% |
Ondrej and Edward are spies and they are going to take down the evil organization AQT. To do so, they will need to infiltrate into the AQT base. The base can be modelled as a tree with $N = 100$ rooms, labelled from 0ドル$ to $N - 1$. Ondrej and Edward’s plan to infiltrate the base is to first get kidnapped and then meet up together before executing their plan. When kidnapped, the two will be placed into different rooms unknown to each other. Once they are placed into the rooms, they will both break free at midnight and try to meet up with each other before executing their plan.
Their plan to meet up is as follows. At every odd minute, Ondrej can choose to stay at his current room or move to an adjacent room. At every even minute, Edward can choose to stay at his current room or move to an adjacent room.
A strategy is defined as the following. Let $V(A, R, T)$ denote the room agent $A$ should be at assuming that they were at room $R$ at midnight and it is currently $T$ minutes after midnight. The strategy should match the conditions above. The agents are said to meet up at time $t(o, e),ドル which is the first time where $V(\text{Ondrej}, o, t(o, e)) = V(\text{Edward}, e, t(o, e))$.
Ondrej and Edward want to meet up as fast as possible, relative to the distance between their two starting rooms. The distance $d(o, e)$ is the minimum number of corridors that must be traversed to reach $o$ from $e$. Please help find a strategy that minimizes the maximum $\frac{t(o,e)}{d(o,e)}$ across all pairs of different rooms $o$ and $e$.
The first line of input will contain $N$ ($N = 100$). If the value of $N$ is anything other than 100ドル,ドル exit the program immediately.
The next $N - 1$ lines will each contain two space-separated integers, denoting the labels of two rooms with a bidirectional corridor between them.
First output a positive number $T,ドル the number of entries per starting room. Note that $T ≤ 1440$ must be satisfied, otherwise you will be awarded no points.
Then, output Ondrej’s strategy, followed by Edward’s strategy.
To output an agent’s strategy, output $N$ lines, where the $n$-th line (starting from 0ドル$) represents the agent’s path if they start at room $n$. For each line, output $T$ spaced integers: The room label that the agent should be in at time 1,ドル 2, \dots , T$.
If the output is invalid or there exists a test case and a pair of different rooms $o$ and $e$ where the agents do not meet at or before time $T,ドル then no points will be awarded.
Otherwise, let $S$ be the maximum among all test cases and pairs of $o$ and $e$ ($o \ne e$) of the value of $\frac{t(o,e)}{d(o,e)}$. The following table shows how the available 25 marks are distributed:
| Score | Bounds on $S$ |
|---|---|
| 3 | 200ドル < S ≤ 1440$ |
| 6 | 100ドル < S ≤ 200$ |
| 8 | 50ドル < S ≤ 100$ |
| 10 | 40ドル < S ≤ 50$ |
| 12 | 30ドル < S ≤ 40$ |
| 15 | 25ドル < S ≤ 30$ |
| 17 | 20ドル < S ≤ 25$ |
| 18 | 19ドル < S ≤ 20$ |
| 19 | 18ドル < S ≤ 19$ |
| 20 | 17ドル < S ≤ 18$ |
| 21 | 16ドル < S ≤ 17$ |
| 22 | 15ドル < S ≤ 16$ |
| 25 | $S ≤ 15$ |
5 0 2 3 2 1 4 2 4
8 2 2 4 4 1 1 1 1 1 1 1 1 1 1 1 1 3 3 2 2 3 3 2 2 3 3 2 2 0 0 2 2 4 4 4 4 2 2 2 2 0 2 2 3 3 3 3 2 1 4 4 2 2 0 0 0 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 1 1 1 1 4 4 4
Note that this is an invalid test case as $N \ne 100,ドル so it will not appear in the test cases when judging. The output for the test case is valid. Note that this would not score any points because if Ondrej starts at room 1ドル$ and Edward starts at room 3ドル,ドル then they will never meet each other.