## NOI '19 P6 - Explore

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
C++

This is an interactive problem.

Given a graph of nodes numbered from to , you need to find all undirected edges through some operations.

Each node has a mark , which is set to initially. now you can apply 4 kinds of operations:

1. modify(x): For node and all of 's direct neighbors, change each node's mark from to ( denotes the exclusive or).

2. query(x): Return the current value of node .

3. report(x,y): Record that there is an edge between and .

4. check(x): Check if all edges incident on have been reported.

For each operation, you can use them at most , , , and times, respectively.

Your job is to implement the function explore(N,M). N and M denote the number of nodes and edges respectively.

With the header explore.h, you can call these four functions:

1. modify(x): There will be no return value. Please make sure .

2. query(x): It will return the value of node . Please make sure .

3. report(x,y): It will record an edge between nodes and . Please make sure .

4. check(x): It will return the status of node . Please make sure . It will return when all edges connected with have been recorded. It will return otherwise.

Note that all graphs are fixed in advance and won't change.

#### Implementation details

##### Interface (API)

To be implemented by contestant:

void explore(int N, int M);


void modify(int p);
int query(int p);
void report(int x, int y);
int check(int x);


There are a total of 25 test cases, each worth 4 points. The constraints for each case is as follows:

1None
2
3
4
5
6A
7
8
9
10B
11
12C
13
14
15D
16
17
18None
19
20
21
22
23
24
25

If a test case is labeled A, then every node in the graph has degree 1.

If a test case is labeled B, then for every node , there exists exactly one node directly connected to it.

If a test case is labeled C, then there exists a permutation of the first nonnegative integers such that two integers are adjacent in the permutation if and only if an edge connects them.

If a test case is labeled D, then the graph is connected.

#### Hint

You can look at the units digit of to distinguish the special graphs from the other cases.