시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 1 1 100.000%

문제

Given a graph of n nodes numbered from 0 to n − 1, you need to find all m undirected edges through some operations.

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 ⊕ 1 (⊕ 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 on x have been reported.

For each operation, you can use them at most Lm, Lq, M, and Lc 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 ≤ x < N.

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

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

  4. check(x): It will return the status of node x. Please make sure 0 ≤ 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.

채점

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

Test Case N = M = Lm = Lq = Lc = Additional Constraints
1 3 2 100 100 100 None
2 100 10N 200 104 2M
3 200 4 × 104
4 300 299 9 × 104
5 500 499 1.5 × 105
6 59998 N/2 17N 17N 0 A
7 99998 18N 18N
8 19998 19N 19N
9
10 99997 N − 1 18N 18N B
11 199997 19N 19N
12 99996 107 107 2M C
13 199996
14
15 99995 D
16
17 199995
18 1004 2000 5 × 104 None
19 3000
20
21 50000 2N 107
22 100000
23 150000 200000
24 200000 250000
25 300000

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.

구현

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);

힌트

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

제출할 수 있는 언어

C++14, C++17, C++2a, C++14 (Clang), C++17 (Clang), C++2a (Clang)

채점

  • 예제는 채점하지 않는다.