NOI '19 P6 - Explore - DMOJ: Modern 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 \leq x < N$ .
query(x): It will return the value $w$ $w$ of node $x$ $x$ . Please make sure $0 \le x < N$ $0 \leq 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 \leq x, y < N$ , $x \ne y$ $x \neq y$ .
check(x): It will return the status of node $x$ $x$ . Please make sure $0 \le x < N$ $0 \leq 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:

Copy

void explore(int N, int M);

Provided for your usage:

Copy

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$ $10 N$	$200$ $200$	$10^4$ $10^{4}$	$2M$ $2 M$
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$ $17 N$	$17N$ $17 N$	$0$ $0$	A
7	$99\,998$ $99 998$		$18N$ $18 N$	$18N$ $18 N$
8	$199\,998$ $199 998$		$19N$ $19 N$	$19N$ $19 N$
9	$199\,998$ $199 998$		$19N$ $19 N$	$19N$ $19 N$
10	$99\,997$ $99 997$	$N-1$ $N - 1$	$18N$ $18 N$	$18N$ $18 N$		B
11	$199\,997$ $199 997$		$19N$ $19 N$	$19N$ $19 N$		B
12	$99\,996$ $99 996$		$10^7$ $10^{7}$	$10^7$ $10^{7}$	$2M$ $2 M$	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$ $2 N$		$10^7$ $10^{7}$
22	$100\,000$ $100 000$	$2N$ $2 N$
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.

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