Description

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.

100 200 300
3 2
0 1
1 2

见“提示与说明”

Hint

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