NOI '22 P3 - Count - DMOJ: Modern Online Judge

NOI '22 P3 - Count

View as PDF

Submit solution

All submissions

Best submissions

Points: 40 (partial)

Time limit: 6.0s

Memory limit: 1G

Problem type

In contest TL 3s, ML 2048MB.

DMOJ Configuration: 6s, ML 1GB (DMOJ only allows for a 1GB memory limit!)

THIS IS AN INTERACTIVE PROBLEM

Given a quintuple $(T, I, S_{V} , S_{E}, \iota)$ ~(T, I, S_{V} , S_{E}, \iota)~ where:

$T$ ~T~ is a rooted tree of n points $T = (V, E)$ ~T = (V, E)~, where $V$ ~V~ is the set of points of $T$ ~T~ and $E$ ~E~ is the edge set of $T$ ~T~. The nodes of the tree are numbered $1, 2, \ldots , n$ ~1, 2, \ldots , n~, where the root node is numbered $1$ ~1~.
$I$ ~I~ is a set, and the elements in the set are called information. There are two different special elements: the UNIT element $\epsilon$ ~\epsilon~ and the ILLEGAL element $\perp$ ~\perp~.

For general information, it has two attributes: VERTEX SET and EDGE SET. For the special case of the identity element, it only has edge set attribute, while for the illegal information, it does not have either of these two attributes.

For information $o \in I \setminus \{\epsilon, \perp\}$ ~o \in I \setminus \{\epsilon, \perp\}~ (the difference $A \ B$ ~A \ B~ of two sets A, B is defined as $A \ B = \{ x \in A \mid x \notin B\}$ ~A \ B = \{ x \in A \mid x \notin B\}~), the VERTEX SET of $o$ ~o~ is a size two subset of V, denoted $S_{V}(o)$ ~S_{V}(o)~. That is, $SV(o) \subseteq V$ ~SV(o) \subseteq V~ and $|SV(o) |=2$ ~|SV(o) |=2~.
For information $o \in I \setminus \{\perp\}$ ~o \in I \setminus \{\perp\}~, the EDGE SET o is a subset of E, denoted $S_{E}(o)$ ~S_{E}(o)~, such that $S_{E}(o) \subseteq E$ ~S_{E}(o) \subseteq E~. Define the edge set of the identity element is empty, that is, $S_E(\epsilon ) = \emptyset$ ~S_E(\epsilon ) = \emptyset~.
For any edge $e \in E$ ~e \in E~ in the tree, denote $e = (u, v)$ ~e = (u, v)~, there is an information about $e$ ~e~, $\iota(e) \in I$ ~\iota(e) \in I~, which takes its endpoints its VERTEX SET and the edge itself as its EDGE SET, that is, $S_{V}(\iota(e)) = {u, v}$ ~S_{V}(\iota(e)) = {u, v}~, and $S_{E}(\iota(e)) = {e}$ ~S_{E}(\iota(e)) = {e}~.

There are two ways that information get combined. Denote them as R and C. They have the following properties

For all $a, b \in I$ ~a, b \in I~, shorthand $r = R(a, b)$ ~r = R(a, b)~, $c = C(a, b)$ ~c = C(a, b)~, such that $r, c \in I$ ~r, c \in I~.

Combining UNIT with any general information gives the other. That is if $a = \epsilon$ ~a = \epsilon~, then $r = c = b$ ~r = c = b~; If $b = \epsilon$ ~b = \epsilon~, then $r = c = a$ ~r = c = a~.
Combining ILLEGAL with ANY information results in illegal information. That is, if $a = \perp$ ~a = \perp~ or If $b = \perp$ ~b = \perp~, then $r = c = \perp$ ~r = c = \perp~.
For the remaining cases, if the intersection of the EDGE SET of the two information is non-empty, or the intersection of the POINT SET of the two information has size that's not 1, the combine results in ILLEGAL. That is, if $S_E(a) \cap S_E(b) \neq \emptyset$ ~S_E(a) \cap S_E(b) \neq \emptyset~ or $|S_V (a) \cap S_V (b)| \neq 1$ ~|S_V (a) \cap S_V (b)| \neq 1~, then $r = c = \perp$ ~r = c = \perp~.
Otherwise, the operations are specified as
- $S_{E}(r) = S_{E}(c) = S_{E}(a) \cup S_{E}(b)$ ,
- $S_{V}(r) = S_{V}(a)$ ~S_{V}(r) = S_{V}(a)~,
- $S_{V}(c) = S_V(a) \oplus S_V(b)$ ~S_{V}(c) = S_V(a) \oplus S_V(b)~.

where $\oplus$ ~\oplus~ represents the symmetric difference operation of sets, that is, $A \oplus B = (A \cup B) \setminus (A \cap B)$ .

Define the on-tree distance of two points in $T$ ~T~ as the number of edges on the tree that a unique simple path traversed by two points as endpoints.

Given the scoring parameter $M$ ~M~ and $q$ ~q~ queries, each query consisting a vertex $u$ ~u~ of the tree and a non-negative integer $d$ ~d~. Denote $X$ ~X~ to be the set of all vertices in $T$ ~T~ whose distances to $u$ ~u~ in the tree does not exceed $d$ ~d~, and $Y = \{ (a, b) \in E \mid a, b \in X\}$ ~Y = \{ (a, b) \in E \mid a, b \in X\}~ to be the set of edges inside $X$ ~X~.

It can be shown that starting from $\epsilon$ ~\epsilon~ and all $L(e)$ ~L(e)~ ( $e \in E$ ~e \in E~), a finite number of R, C calls produces an information $o$ ~o~ such that $o \neq \perp$ ~o \neq \perp~ and $S_{E}(o) = Y$ ~S_{E}(o) = Y~. In particular, if $d = 0$ ~d = 0~, you the output should be the UNIT element $\epsilon$ ~\epsilon~.

In each set of queries, you need to construct an information $o$ ~o~ that satisfies this requirement, subject to the limit that the sum of the calls to $R$ ~R~ and $C$ ~C~ does not exceed $M$ ~M~.

Implementation Details

Files can be found here.

Make sure you #include count.h at the beginning of your program. The header file count.h implements the following:

Define the data type info corresponding to the information;
Define the info type constant emptyinfo corresponding to $\epsilon$ ~\epsilon~, which you can use directly in the program.
The following two information merging functions, which you can call directly in the program:
```
1 info MR(info a, info b);
2 info MC(info a, info b);
```
The two functions return the information corresponding to $R(a, b)$ ~R(a, b)~ and $C(a, b)$ ~C(a, b)~, respectively. You need to ensure that calling $R(a, b)$ ~R(a, b)~ or $C(a, b)$ ~C(a, b)~ does not result in $\perp$ ~\perp~, otherwise the program may behave unexpectedly.
A function to determine whether a information is UNIT, you can call it directly in the program:
```
bool isempty(info a);
```
This function returns true if and only if a is an identity element. See the reference interaction library for more implementation details.

You do not need to, and should not, implement main();

You need to implement the following functions:

void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);

$T$ ~T~ is the test point number, $n$ ~n~ is the number of points in the tree, $q$ ~q~ is the number of queries, and $M$ ~M~ is the scoring parameter for that test point.
Both fa and e have length $n - 1$ ~n - 1~. For $0 \leq i < n - 1$ ~0 \leq i < n - 1~, fa[i] and i + 2 are the two endpoints of the i-th edge $e_{i}$ ~e_{i}~, and $e_i$ ~e_i~ is the info type element corresponding to $\iota(e_i)$ ~\iota(e_i)~ mentioned in the title description. The data guarantees that $fa_i$ ~fa_i~ is less than $i + 2$ ~i + 2~.

info ask(int u, int d);

Give a query, see the question description for the meaning of the parameters. You need to return a information that satisfies the condition of the question at the end of the function.

When testing, at each test case, the interactive library will call the init function exactly once, and then call the ask function $q$ ~q~ times. The interactive library will use a special implementation, a single info type variable will constantly consume $12$ ~12~ bytes of memory,

It is guaranteed that under the condition that the number of calls is satisfied and the isempty function is not called, the time required for the interactive library to run in the final test does not exceed $0.6$ ~0.6~ seconds, and the memory consumed by the interactive library itself does not exceed 16 MiB. It is guaranteed that the final tested interactive library will take no more than $0.25$ ~0.25~ seconds to run with at most $10^{8}$ ~10^{8}~ isempty function calls.

A file named count.cpp is included in the issued files: you may use it.

Testing

The reference materials provides of two interactive libraries grader.o and checker.o are provided in this topic directory, which are linkable files generated by compiling two different interactive libraries. The implementation of the interaction library used in the final test is different from this implementation, so the solution of the contestant should not depend on the specific implementation of the interaction library, nor should it depend on the specific implementation of the info type in count.h.

You need to modify the distributed count.h to help with linking. Specifically, when linking the source code count.cpp with the program grader.o, you need to comment out the 5th line of the count.h code and keep the 4th line of code. Linking the checker.o method is similar, you need to comment out the 4th line of the count.h code and keep the 5th line of code. Players can modify the implementation of count.h by themselves to compile different programs.

After modification, the contestant can use the following command to compile the executable program in the directory of this question:

g++ count.cpp ‐c ‐O2 ‐std=c++14 ‐lm && g++ count.o grader.o ‐o count
g++ count.cpp ‐c ‐O2 ‐std=c++14 ‐lm && g++ count.o checker.o ‐o count

The first command line will compile the current count.cpp and link it with grader.o to generate the executable file count. The second line command will compile the current count.cpp and link it with checker.o to generate the executable file count.

The executable file count obtained by compiling the above method runs as follows:

The executable will read data in the following format from standard input:
The first line contains four integers $id, n, q, M$ ~id, n, q, M~, which represent the test point number, the number of points in the tree, the number of queries, and the scoring parameter;
In the second line, n - 1 integers $p_2, p_3, \ldots , p_n$ ~p_2, p_3, \ldots , p_n~ represent the parent node numbers from $2$ ~2~ to $n$ ~n~, respectively. When debugging locally, you need to ensure that $\forall i \in [2, n]$ ~\forall i \in [2, n]~, $p_i < i$ ~p_i < i~;
The next $q$ ~q~ lines contain two integers $u, d$ ~u, d~ each, describing a query.

After being read in, the interactive library is tested. If your program does not meet the interactive library limit, the output will return the corresponding error. Otherwise, for the linked executable, the output is as follows:

A total of three integers $C1, C2, C3$ ~C1, C2, C3~ on one line, where: ∗ $C1$ ~C1~ represents the total number of times the program calls the interactive library function in the init function; ∗ $C2$ ~C2~ represents the total number of times the program calls interactive library functions during running; ∗ * $C3$ ~C3~ represents the maximum number of times the program calls the interactive library function in q times of ask functions.
For the above three statistics, we only count the number of calls of the MR and MC functions, but not the number of calls of the isempty function.
When linking different files, the checks they can perform are also different, specifically:
grader.o : It does not check whether the information returned by the ask function is correct at runtime, but it can help players determine whether the interaction meets the requirements. The running time of this program is closest to the interactive library at the time of evaluation, so players can use this program to test the running speed, but the correctness of the program is not guaranteed.
checker.o : It will check whether the information returned by the ask function is correct at runtime, and can also help players determine whether the interactive operation meets the requirements. At the same time, it will check whether the information returned by the ask function is correct. This program can check the correctness of the answers.

Samples

See count{1,2,3,4}.{in, ans}

Samples 2 & 3 satisfy special properties A and B (see below) respectively

NOTE:

An uninitialized variable of type info is not guaranteed to be emptyinfo.
Please do not try to access or modify member variables of type info, otherwise it will be regarded as attacking the interactive library.
Please do not call the MR and MC functions before the init function call, otherwise undefined behavior may occur.
You can only access the variables defined by yourself and the info type variables returned by the interactive library. Trying to access other spaces may result in compilation errors or runtime errors.

This question will first be subject to the same restrictions as traditional questions. For example, compilation errors will result in 0 points for the entire question, and runtime errors, exceeding the time limit, exceeding the space limit, etc. will result in 0 points for the corresponding test points, etc. In addition to the above conditions, a test point will receive a score of 0 if the program executes an illegal function call or gives an incorrect answer in a query operation. Otherwise, denote $C1$ ~C1~ and $C3$ ~C3~ as the number of times your program calls the interactive library function in the init function, and the maximum number of times your program calls the interactive library function in all q ask functions. If $C1 \leq 3 · 10^{7}$ ~C1 \leq 3 · 10^{7}~ and $C3$ ~C3~ does not exceed the scoring parameter $M$ ~M~ for that test point, you will get a score for that test point, otherwise you can't get a score for that test point. Note: When calculating $C1$ ~C1~ and $C3$ ~C3~, only the number of calls of the MR and MC functions will be counted, but not the number of calls of the isempty function.

Constraints

For all test cases, $1 \leq n \leq 2 \times 10^5$ ~1 \leq n \leq 2 \times 10^5~, $1 \leq q \leq 10^6$ ~1 \leq q \leq 10^6~, for each query, $1 \leq u \leq n$ ~1 \leq u \leq n~, $1 \leq d \leq n-1$ ~1 \leq d \leq n-1~.

TestCase	$n=$ ~n=~	$q=$ ~q=~	Property	$M=$ ~M=~
$1$ ~1~	$1000$ ~1000~	$10^4$ ~10^4~		$500$ ~500~
$2$ ~2~	$2000$ ~2000~	$10^4$ ~10^4~		$500$ ~500~
$3,4$ ~3,4~	$10^5$ ~10^5~	$10^6$ ~10^6~	A	$5$ ~5~
$5,6$ ~5,6~	$6 \times 10^4$ ~6 \times 10^4~	$6\times 10^4$ ~6\times 10^4~	B	$50$ ~50~
$7$ ~7~	$6 \times 10^4$ ~6 \times 10^4~	$6 \times 10^4$ ~6 \times 10^4~	B	$5$ ~5~
$8$ ~8~	$10^5$ ~10^5~	$10^5$ ~10^5~	B	$5$ ~5~
$9$ ~9~	$7500$ ~7500~	$5 \times 10^4$ ~5 \times 10^4~	C	$500$ ~500~
$10$ ~10~	$10^4$ ~10^4~	$5 \times 10^4$ ~5 \times 10^4~		$500$ ~500~
$11$ ~11~	$1.5 \times 10^4$ ~1.5 \times 10^4~	$5 \times 10^4$ ~5 \times 10^4~		$500$ ~500~
$12$ ~12~	$2 \times 10^4$ ~2 \times 10^4~	$5 \times 10^4$ ~5 \times 10^4~		$50$ ~50~
$13$ ~13~	$2.5 \times 10^4$ ~2.5 \times 10^4~	$5 \times 10^4$ ~5 \times 10^4~		$5$ ~5~
$14$ ~14~	$3 \times 10^4$ ~3 \times 10^4~	$10^5$ ~10^5~		$5$ ~5~
$15$ ~15~	$6 \times 10^4$ ~6 \times 10^4~	$10^6$ ~10^6~	D	$5$ ~5~
$16$ ~16~	$6 \times 10^4$ ~6 \times 10^4~	$10^6$ ~10^6~		$5$ ~5~
$17$ ~17~	$8 \times 10^4$ ~8 \times 10^4~	$10^6$ ~10^6~		$5$ ~5~
$18$ ~18~	$10^5$ ~10^5~	$10^6$ ~10^6~		$5$ ~5~
$19$ ~19~	$1.5 \times 10^5$ ~1.5 \times 10^5~	$10^6$ ~10^6~		$5$ ~5~
$20$ ~20~	$2 \times 10^5$ ~2 \times 10^5~	$10^6$ ~10^6~		$1$ ~1~

Property A: For all $i = 1,2,...,n-1$ ~i = 1,2,...,n-1~, the parent of $(i+1)$ ~(i+1)~ is $i$ ~i~.
Property B: For all queries, $u = 1$ ~u = 1~.
Property C: For all queries, $d <= 100$ ~d <= 100~.
Property D: For all queries, $d >= 1000$ ~d >= 1000~.

Comments

There are no comments at the moment.