P5473 [NOI2019] Mr. I's Adventure.

Additional files can be downloaded from “Attachments” at the bottom of the page. ### Special Notes **Notes for submitting this problem on Luogu (if it differs from the original statement, follow what is written here):** 1. Unlike the original problem, you do not need to, and should not, include the header file `explore.h` at the beginning of your program. 2. To ensure your program compiles correctly, you need to add the following function declarations at the beginning of your submitted program: ```cpp void modify(int x); int query(int x); void report(int x, int y); int check(int x); ``` 3. This problem only supports submissions in C++ (including `C++`, `C++11`, `C++14`, `C++17`).

Half a year later, Mr. I’s shop finally could not stay open anymore. He decided to transfer the shop and become an explorer to explore the vast unknown world. According to ancient books, he found an underground palace created by an unknown civilization deep in a great desert. The palace consists of $N$ large caves and $M$ bidirectional passages connecting these caves. Mr. I can use the ancient book to identify which cave he is in, but the book does not record the connection structure of the $M$ passages, so it is difficult for him to search for the endless treasure said to be hidden in the palace. However, Mr. I has now found a mysterious mechanism that can reveal information about the palace. Mr. I decides to use this mechanism to obtain the connection structure of the palace, and asks you to assist him. The underground palace can be abstracted as an undirected simple graph with $N$ vertices and $M$ edges (a simple graph means there is at most one directly connected edge between any two vertices). The caves are numbered from $0 \sim n - 1$. Currently, you do not know what the edges are. Each cave has a light source, which has two states: on and off. A cave is lit only when its light source is on. Initially, all light sources are off, and the light states can only be changed using the mysterious mechanism discovered by Mr. I. More specifically, the mechanism supports the following four operations: 1. Given an index $x$, the mechanism will toggle the light state of cave $x$ and all caves that are directly connected to cave $x$ by a passage. That is, lights that were on will be turned off, and lights that were off will be turned on. 2. Given an index $x$, the mechanism will display the current light state of cave $x$. 3. Given two indices $x, y$, it means you confirm that there is a passage connecting cave $x$ and cave $y$, and you ask the mechanism to record it. 4. Given an index $x$, the mechanism will determine whether all passages incident to cave $x$ have already been recorded. The mechanism can perform the next operation only after finishing the previous one. The mechanism cannot be used freely, so the number of times each operation can be used is limited to $L_m, L_q, M, L_c$, respectively. Your task is to write a program to help Mr. I decide how to use the mechanism properly, so that all $M$ passages can be found correctly. ### Implementation Details You do not need to, and should not, implement the main function. You only need to implement the function `explore(N, M)`, where $N$ and $M$ are the numbers of caves and passages. You can interact with the interactive library by calling the following four functions: 1. `modify(x)` - This function makes the mechanism perform operation $1$ with the given index $x$. - You must ensure $0 \leq x < N$. This function has no return value. 2. `query(x)` - This function makes the mechanism perform operation $2$ with the given index $x$. - You must ensure $0 \leq x < N$. This function returns $0$ or $1$, meaning the light source of cave $x$ is currently off ($0$) or on ($1$). 3. `report(x, y)` - This function makes the mechanism perform operation $3$ with the given indices $x, y$. - You must ensure $0 \leq x, y < N$ and $x \neq y$. This function has no return value. 4. `check(x)` - This function makes the mechanism perform operation $4$ with the given index $x$. - You must ensure $0 \leq x < N$. This function returns $0$ or $1$, where it returns $1$ if and only if all passages incident to cave $x$ have already been recorded via operation 3. During judging, the interactive library will call `explore` exactly once. This problem guarantees that the graph used has been fully determined before the interaction starts, and will not be constructed dynamically based on the interaction process. Therefore, all interactive operations in the statement are deterministic, and you do not need to care about their internal implementation in the library. The testdata guarantees that under the call limits, the time needed for the interactive library to run does not exceed 1 s. The memory used by the interactive library is fixed and does not exceed 128 MB. ### Implementation Method A `template_explore.cpp/c/pas` has already been provided in the contestant working directory. Please copy this file and rename it to `explore.cpp/c/pas`, then solve the problem based on it. 1. For C++ / C contestants - Please make sure your program starts with ``` #include "explore.h"。 ``` - The interface of the function `explore` you need to implement is: ``` void explore(int N, int M); ``` - The interfaces of the interactive functions you can call are: ``` void modify(int x); int query(int x); void report(int x, int y); int check(int x); ``` 2. For Pascal contestants - Note: The syntax for implementing the interface in Pascal code is relatively complex. Please solve the problem directly based on the provided `template_explore.pas`, rather than implementing everything from scratch. - The interface of the function you need to implement is: ``` procedure _explore(N, M : longint); ``` - Note: The function name here is `_explore` rather than `explore`. Using `explore` will cause compilation failure. - The interfaces of the interactive functions you can call are: ``` procedure modify(x : longint); function query(x : longint) : longint; procedure report(x : longint; y : longint); function check(x : longint) : longint; ``` The `grader.cpp/c` and `graderhelperlib.pas` in the problem directory are a reference implementation of the interactive library provided by us. The interactive library used in the final test is different from this reference implementation, so your solution should not depend on the library implementation. 1. For `C/C++` contestants: - You need to compile the executable in this problem directory using the following commands: - For C: ``` gcc grader.c explore.c -o explore -O2 -lm ``` - For C++: ``` g++ grader.cpp explore.cpp -o explore -O2 -lm ``` 2. For `Pascal` contestants: - You need to compile the executable in this problem directory using the following command: ``` fpc grader.pas -o"explore" -O2 ``` 3. For the compiled executable: - The executable will read input from standard input in the following format: The first line contains three integers $L_m, L_q, L_c$. The second line contains two integers $N, M$, with the meanings as described above. The next $M$ lines each contain two integers $x, y$, describing a passage connecting cave $x$ and cave $y$. - After reading is finished, the interactive library will call the function `explore` exactly once, and test your function with the input data. After your function returns correctly, the interactive library will check whether your result is correct. If it is correct, it will output `Correct` and information related to the number of interactive calls; otherwise it will output the corresponding error information.

N/A

N/A

The three integers on the first line of the testdata are the call limits of the three operations: the number of calls to `modify(x)` must not exceed $100$, the number of calls to `query(x)` must not exceed $200$, and the number of calls to `check(x)` must not exceed $300$. The two integers on the second line of the testdata are the number of caves and the number of passages, i.e. $N = 3 , M = 2$. The number of calls to `report(x, y)` must not exceed $M$, so in this example it must not exceed $2$ calls. Below is a correct interaction process: | Contestant Program | Interactive Library | Explanation | | :----------: | :----------: | :----------: | | | Calls $\text{explore}(3,2)$ | Start testing. | | Calls $\text{modify}(0)$ | | Perform operation $1$ on cave $0$. | | Calls $\text{query}(2)$ | Returns $0$ | The current light state of cave $2$ is off. | | Calls $\text{report}(0,1)$ | | Found and recorded the passage $(0,1)$. | | Calls $\text{check}(0)$ | Returns $1$ | All passages incident to cave $0$ have been recorded. | | Calls $\text{report}(2,1)$ | | Found and recorded the passage $(2,1)$. | | Ends and returns | Prints $\text{Correct}$ | Interaction ends, and the result is correct. | ### Notes on Provided Files In this problem directory: 1. `grader.cpp/c` and `graderhelperlib.pas` are the reference implementation of the interactive library provided by us. 2. `explore.h` and `grader.pas` are header files; contestants do not need to care about their contents. 3. `template_explore.cpp/c/pas` is the sample solution source code provided by us. 4. `explore1.in`, `explore2.in`, `explore3.in` are sample inputs for testing. Please back up all provided files. The judge only collects `explore.c/cpp/pas` in this problem directory, and any modifications to other files are ignored. The final judging will only collect `explore.cpp/c/pas`. Modifying other files in your directory does not affect judging. This problem is first subject to the same limits as traditional problems. For example, compilation errors will make the whole problem score $0$ points, runtime errors, time limit exceeded, memory limit exceeded, etc. will make the corresponding test point score $0$ points. You may only access variables you define and those provided by the interactive library, as well as their corresponding memory space. Attempting to access other memory may cause compilation errors or runtime errors. Under the above conditions, for each test point, you get full score if and only if: 1. Every function call you make is valid, and the numbers of calls to `modify`, `query`, and `check` do not exceed $L_m, L_q, L_c$, respectively. 2. Since the call limit of `report` is $M$, each call must record a new edge that exists. That is, each time you call `report(x, y)`, it must satisfy: there is a passage connecting caves $x$ and $y$, and before this call you have never called `report(x, y)` or `report(y, x)`. 3. The function `explore` you implemented returns normally. 4. When `explore` returns, you have recorded all $M$ passages by calling `report`. There are $25$ test points in total, each worth $4$ points. The data size and related limits for each test point are shown in the table below. | Test Point ID | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | Special Property | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | None | | $2$ | $100$ | $10\times N$ | $200$ | $10^4$ | $2\times M$ | None | | $3$ | $200$ | $10\times N$ | $200$ | $4\times 10^4$ | $2\times M$ | None | | $4$ | $300$ | $10\times N$ |$299$ | $9\times 10^4$ | $2\times M$ | None | | $5$ | $500$ | $10\times N$ | $499$ | $1.5\times 10^5$ | $2\times M$ | None | | $6$ | $59998$ | $\frac{N}{2}$ | $17\times N$ | $17\times N$ | $0$ | $A$ | | $7$ | $99998$ | $\frac{N}{2}$ | $18\times N$ | $18\times N$ | $0$ | $A$ | | $8$ | $199998$ | $\frac{N}{2}$ | $19\times N$ | $19\times N$ | $0$ | $A$ | | $9$ | $199998$ | $\frac{N}{2}$ | $19\times N$ | $19\times N$ | $0$ | $A$ | | $10$ | $99997$ | $N-1$ | $18\times N$ | $18\times N$ | $0$ | $B$ | | $11$ | $199997$ | $N-1$ | $19\times N$ | $19\times N$ | $0$ | $B$ | | $12$ | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $C$ | | $13$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $C$ | | $14$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $C$ | | $15$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $D$ | | $16$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $D$ | | $17$ | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2\times M$ | $D$ | | $18$ | $1004$ | $2\times 10^3$ | $10^7$ | $5\times 10^4$ | $2\times M$ | None | | $19$ | $1004$ | $3\times 10^3$ | $10^7$ | $$5\times 10^4$$ | $2\times M$ | None | | $20$ | $1004$ | $3\times 10^3$ | $10^7$ | $5\times 10^4$ | $2\times M$ | None | | $21$ | $5\times 10^4$ | $2\times N$ | $10^7$ | $10^7$ | $2\times M$ | None | | $22$ | $10^5$ | $2\times N$ | $10^7$ | $10^7$ | $2\times M$ | None | | $23$ | $1.5\times 10^5$ | $2\times 10^5$ | $10^7$ | $10^7$ | $2\times M$ | None | | $24$ | $2\times 10^5$ | $2.5\times 10^5$ | $10^7$ | $10^7$ | $2\times M$ | None | | $25$ | $2\times 10^5$ | $3\times 10^5$ | $10^7$ | $10^7$ | $2\times M$ | None | Reminder again: the problem guarantees that the graph used for testing has been fully determined before the interaction starts, and will not be constructed dynamically based on the interaction with your program. The meanings of the variables in the “Special Property” column are as follows: A: It is guaranteed that the degree of every vertex is exactly $1$. B: It is guaranteed that for every $x > 0$, there exists exactly one $y < x$ such that cave $x$ is directly connected to cave $y$ by a passage. C: There exists a permutation $p_0, p_1, \cdots , p_{N-1}$ of $0 \sim N - 1$ such that for any $1 \leq i < N$, there exists a passage connecting caves $p_{i-1}$ and $p_i$. D: It is guaranteed that the graph is connected. - Hint: Your program can distinguish the different data types above by checking the last digit of the given $N$. Translated by ChatGPT 5