This is an interactive problem.
Given an undirected simple graph of nodes numbered from to , you need to find all undirected edges through some operations. Note that a simple graph has no self-loops, and any pair of vertices have at most edge between them.
Each node has a mark , which is set to initially. Now you can apply 4 kinds of operations:
modify(x)
: For node and all of 's direct neighbors, change each node's mark from to ( denotes the exclusive or).query(x)
: Return the current value of node .report(x,y)
: Record that there is an edge between and .check(x)
: Check if all edges incident to 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:
modify(x)
: There will be no return value. Please make sure .query(x)
: It will return the value of node . Please make sure .report(x,y)
: It will record an edge between nodes and . Please make sure , .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);
Provided for your usage:
void modify(int p);
int query(int p);
void report(int x, int y);
int check(int x);
Grading
There are a total of 25 test cases, each worth 4 points. The constraints for each case is as follows:
Test Case | Additional Constraints | |||||
---|---|---|---|---|---|---|
1 | None | |||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | A | |||||
7 | ||||||
8 | ||||||
9 | ||||||
10 | B | |||||
11 | ||||||
12 | C | |||||
13 | ||||||
14 | ||||||
15 | D | |||||
16 | ||||||
17 | ||||||
18 | None | |||||
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.
Comments
are self loops allowed? (if x has edge to x, does w[x] not change when one calls modify(x)?)
地下宫殿可以抽象成一张 𝑁 个点、𝑀 条边的无向简单图(简单图满足任意两点之间至多存在一条直接相连的边)。