NOI '19 P6 - Explore - Olympiads Online Judge

NOI '19 P6 - Explore

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

Allowed languages

C++

This is an interactive problem.

Given an undirected simple graph of $N$ ~N~ nodes numbered from $0$ ~0~ to $N-1$ ~N-1~, you need to find all $M$ ~M~ undirected edges through some operations. Note that a simple graph has no self-loops, and any pair of vertices have at most $1$ ~1~ edge between them.

Each node has a mark $w$ ~w~, which is set to $0$ ~0~ initially. Now you can apply 4 kinds of operations:

modify(x): For node $x$ ~x~ and all of $x$ ~x~'s direct neighbors, change each node's mark from $w$ ~w~ to $w \oplus 1$ ~w \oplus 1~ ( $\oplus$ ~\oplus~ denotes the exclusive or).
query(x): Return the current $w$ ~w~ value of node $x$ ~x~.
report(x,y): Record that there is an edge between $x$ ~x~ and $y$ ~y~.
check(x): Check if all edges incident to $x$ ~x~ have been reported.

For each operation, you can use them at most $L_m$ ~L_m~, $L_q$ ~L_q~, $M$ ~M~, and $L_c$ ~L_c~ 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 $0 \le x < N$ ~0 \le x < N~.
query(x): It will return the value $w$ ~w~ of node $x$ ~x~. Please make sure $0 \le x < N$ ~0 \le x < N~.
report(x,y): It will record an edge between nodes $x$ ~x~ and $y$ ~y~. Please make sure $0 \le x, y < N$ ~0 \le x, y < N~, $x \ne y$ ~x \ne y~.
check(x): It will return the status of node $x$ ~x~. Please make sure $0 \le x < N$ ~0 \le x < N~. It will return $1$ ~1~ when all edges connected with $x$ ~x~ have been recorded. It will return $0$ ~0~ 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	$N =$ ~N =~	$M =$ ~M =~	$L_m =$ ~L_m =~	$L_q =$ ~L_q =~	$L_c =$ ~L_c =~	Additional Constraints
1	$3$ ~3~	$2$ ~2~	$100$ ~100~	$100$ ~100~	$100$ ~100~	None
2	$100$ ~100~	$10N$ ~10N~	$200$ ~200~	$10^4$ ~10^4~	$2M$ ~2M~
3	$200$ ~200~		$200$ ~200~	$4 \times 10^4$ ~4 \times 10^4~
4	$300$ ~300~		$299$ ~299~	$9 \times 10^4$ ~9 \times 10^4~
5	$500$ ~500~		$499$ ~499~	$1.5 \times 10^5$ ~1.5 \times 10^5~
6	$59\,998$ ~59\,998~	$\frac N 2$ ~\frac N 2~	$17N$ ~17N~	$17N$ ~17N~	$0$ ~0~	A
7	$99\,998$ ~99\,998~		$18N$ ~18N~	$18N$ ~18N~
8	$199\,998$ ~199\,998~		$19N$ ~19N~	$19N$ ~19N~
9	$199\,998$ ~199\,998~		$19N$ ~19N~	$19N$ ~19N~
10	$99\,997$ ~99\,997~	$N-1$ ~N-1~	$18N$ ~18N~	$18N$ ~18N~		B
11	$199\,997$ ~199\,997~		$19N$ ~19N~	$19N$ ~19N~		B
12	$99\,996$ ~99\,996~		$10^7$ ~10^7~	$10^7$ ~10^7~	$2M$ ~2M~	C
13	$199\,996$ ~199\,996~
14	$199\,996$ ~199\,996~
15	$99\,995$ ~99\,995~					D
16	$99\,995$ ~99\,995~
17	$199\,995$ ~199\,995~
18	$1\,004$ ~1\,004~	$2\,000$ ~2\,000~		$5 \times 10^4$ ~5 \times 10^4~		None
19		$3\,000$ ~3\,000~
20		$3\,000$ ~3\,000~
21	$50\,000$ ~50\,000~	$2N$ ~2N~		$10^7$ ~10^7~
22	$100\,000$ ~100\,000~	$2N$ ~2N~
23	$150\,000$ ~150\,000~	$200\,000$ ~200\,000~
24	$200\,000$ ~200\,000~	$250\,000$ ~250\,000~
25	$200\,000$ ~200\,000~	$300\,000$ ~300\,000~

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 $x > 0$ ~x > 0~, there exists exactly one node $y < x$ ~y < x~ directly connected to it.

If a test case is labeled C, then there exists a permutation of the first $N$ ~N~ 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 $N$ ~N~ to distinguish the special graphs from the other cases.

Comments

2

rpeng commented on Aug. 7, 2021, 3:38 p.m.

are self loops allowed? (if x has edge to x, does w[x] not change when one calls modify(x)?)

1

chika commented on Aug. 7, 2021, 6:59 p.m.

地下宫殿可以抽象成一张 𝑁 个点、𝑀 条边的无向简单图（简单图满足任意两点之间至多存在一条直接相连的边）。