NOI '19 P6 - Explore

View as PDF

Submit solution

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 nodes numbered from 0 to N-1, you need to find all M undirected edges through some operations. Note that a simple graph has no self-loops, and any pair of vertices have at most 1 edge between them.

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

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

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

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

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

For each operation, you can use them at most L_m, L_q, M, and 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:

  1. modify(x): There will be no return value. Please make sure 0 \le x < N.

  2. query(x): It will return the value w of node x. Please make sure 0 \le x < N.

  3. report(x,y): It will record an edge between nodes x and y. Please make sure 0 \le x, y < N, x \ne y.

  4. check(x): It will return the status of node x. Please make sure 0 \le x < N. It will return 1 when all edges connected with x have been recorded. It will return 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 CaseN =M =L_m =L_q =L_c =Additional Constraints
132100100100None
210010N20010^42M
32004 \times 10^4
43002999 \times 10^4
55004991.5 \times 10^5
659\,998\frac N 217N17N0A
799\,99818N18N
8199\,99819N19N
9
1099\,997N-118N18NB
11199\,99719N19N
1299\,99610^710^72MC
13199\,996
14
1599\,995D
16
17199\,995
181\,0042\,0005 \times 10^4None
193\,000
20
2150\,0002N10^7
22100\,000
23150\,000200\,000
24200\,000250\,000
25300\,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, there exists exactly one node y < x directly connected to it.

If a test case is labeled C, then there exists a permutation of the first 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 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.

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