P9733 [CEOI 2023] The Ties That Guide Us (incursion)

You hired an assistant with the profit from your vending robots, and now you are ready to take the safe containing the CEOI medals. The safe is located in a university building consisting of $n$ rooms, connected by $n-1$ doors. Every room is reachable from any other room, and each room is connected to at most $3$ doors. Both you and your assistant have a floor plan describing how the rooms are connected, but although your two plans describe the same structure, the numbering of rooms and doors may be different. On the second day of the contest, the committee is busy handling announcements and contestants' questions. This will be a perfect chance to get close to the safe with the medals. Your assistant will first search the whole building. Once he finds the room containing the safe, he will leave you hints on how to get to that room. Since phones cannot be brought into the contest area, he uses an almost unlimited supply of identical ties left over from last year's BOI. Because these ties are indistinguishable, the only information you can obtain is the number of ties he left in any given room. Since too many ties in one room would be very suspicious, the maximum number of ties in any single room should be as small as possible (see the scoring section). After that, you plan to sneak out while going to the bathroom, and use the ties your assistant left to find the room with the safe. The safe is hidden in a room, so when you enter the room containing the safe, you must be able to identify that room using only the ties; moreover, since staying “in the bathroom” for too long would be noticed, you must find the safe as quickly as possible. You may traverse at most $d+30$ doors, where $d$ is the number of doors on the shortest path from your initial position to the safe. If you traverse the same door multiple times, each traversal is counted. Therefore, you need to write a program that tells your assistant how many ties to leave in each room, and guides you to the room containing the safe.

This is an interactive function problem. For each test case, your program will be run twice. You need to implement the following two functions (function prototypes are given): ``` vector mark(vector F, int safe); ``` - $F$: contains $n-1$ pairs $(u,v)$, where $1 \le u,v \le n$ and it is guaranteed that $u \neq v$, meaning that on your assistant's map, room $u$ and room $v$ are connected by a door. - $\mathrm{safe}$: the room number of the safe on your assistant's map. This function should return a `vector` $v$ of length $n$, where each element $v_i$ is the number of ties your assistant should leave in room $i+1$ on his map. You should guarantee $0 \le v_i \le 10^9$. ``` void locate(vector F,int curr,int t); ``` - $F$: contains $n-1$ pairs $(u,v)$, where $1 \le u,v \le n$ and it is guaranteed that $u \neq v$, meaning that on your map, room $u$ and room $v$ are connected by a door. - $\mathrm{curr}$: the room number where you are currently located. - $t$: the number of ties found in the room you are currently in. In the description below, room numbers follow your map's numbering. While implementing the function `locate`, you may call the following function: ``` int visit(int v); ``` to move from your current room $u$ to an adjacent room $v$. You must ensure the operation is legal, i.e. $1 \le v \le n,(u,v) \in F\:\vee (v,u) \in F$. This function returns a non-negative integer $k$, meaning the number of ties you find in room $v$. The number of calls to this function must not exceed $d+30$, where $d$ is the shortest distance from your start to your destination. When the function `locate` terminates, you should be in the room containing the safe. For each test case, in the first run the program calls `mark`, and in the second run it calls `locate`. If `visit` is called too many times, called illegally, or called in `mark`, your program will be terminated and the submission will be judged **Wrong Answer**. Your program must not read from or write to `stdin` or `stdout`, otherwise it will be judged **Security Violation**. However, you may print anything to `stderr`. You need to add `#include "incursion.h"` at the beginning of your source code file. You should link your program with `sample_grader.cpp` for local testing. Below is an explanation of the sample grader. Please refer to `sample_grader.cpp` for the operation details. For simplicity, this grader will not run your program twice; instead, in a single run it calls each of the two functions once. The attachment contains an example implementation of `sample_grader.cpp`. Note: this implementation is not the same as the one used in the actual judging. It is forbidden to try to pass this task by hacking the grader.

N/A

### Scoring Rules There are 4 subtasks. For each test case, $2 \le n \le 45000$. Subtask 1 (30 points): it is guaranteed that no room is connected to $3$ doors. Subtask 2 (30 points): there is exactly one room connected to $2$ doors. Subtask 3 (40 points): no special properties. For each test case, suppose the room using the most ties uses $T_{\max}$ ties: - If $T_{\max}