P8532 [Ynoi2003] Kirisame Marisa

**This is an interactive problem.** **Before submitting this problem, please read the following carefully.** This problem only supports C++ submissions (C++14 is recommended; please do not use C++14 (GCC9)). Due to Luogu’s special interaction mechanism, when submitting this problem, please remove the line `#include "count.h"` from your code, and paste the content of the provided file **`count_.h`** (note that it is not `count.h` inside `count.zip`) at the very beginning of your code, then submit. If you cannot open `count_.h`, you may copy the following content. ```cpp #ifndef CIRCLE_H #define CIRCLE_H #include struct info{ unsigned val; unsigned poi[2]; }; const info emptyinfo=info{0,(unsigned)-1,(unsigned)-1}; info MR(info a,info b); info MC(info a,info b); void init(int T,int n,int q,std::vectordad,std::vectorve,int M); bool isempty(info a); info ask(int x,int d); #endif ``` If anything unexpected happens when you submit this problem, please contact an administrator.

You are given a 5-tuple $(T, I, S_V, S_E, \iota)$, where: - $T$ is a rooted tree with $n$ vertices, $T = (V, E)$, where $V$ is the vertex set and $E$ is the edge set. The vertices are numbered $1, 2, \ldots, n$, and the root is vertex $1$. - $I$ is a set, whose elements are called **information**. There are two distinct special elements: the identity element $\epsilon$ and the invalid information $\bot$. For general information, it has two attributes: a **vertex set** and an **edge set**. In particular, the identity element only has an edge-set attribute, while the invalid information has neither attribute. - For information $o \in I \setminus \{ \epsilon, \bot \}$, the **vertex set** of $o$ is a 2-element subset of $V$, denoted $S_V(o)$, satisfying $S_V(o) \subseteq V$ and $\lvert S_V(o) \rvert = 2$. For two sets $A, B$, the difference $A \setminus B$ is defined as $A \setminus B = \{ x \in A \hspace{3mu}\vert\hspace{3mu} x \notin B \}$. - For information $o \in I \setminus \{ \bot \}$, the **edge set** of $o$ is a subset of $E$, denoted $S_E(o)$, satisfying $S_E(o) \subseteq E$. The edge set of the identity element is defined to be empty, i.e. $S_E(\epsilon) = \varnothing$. - For any edge $e \in E$ on the tree, let $e = (u, v)$. There exists an information $\iota(e) \in I$ associated with $e$, which takes its endpoints as the vertex set and itself as the edge set, i.e. $S_V(\iota(e)) = \{ u, v \}$ and $S_E(\iota(e)) = \{ e \}$. There are two ways to merge information, denoted $R$ and $C$. For $\forall a, b \in I$, let $r = R(a, b)$ and $c = C(a, b)$, with $r, c \in I$. Then: - Merging the identity element with any information yields the other one. That is, if $a = \epsilon$ then $r = c = b$; if $b = \epsilon$ then $r = c = a$. - Merging invalid information with any information yields invalid information. That is, if $a = \bot$ or $b = \bot$, then $r = c = \bot$. - In the remaining cases, if the intersection of the **edge sets** is non-empty, or the size of the intersection of the **vertex sets** is not $1$, then the merge result is invalid information. That is, if $S_E(a) \cap S_E(b) \ne \varnothing$ or $\lvert S_V(a) \cap S_V(b) \rvert \ne 1$, then $r = c = \bot$. - Otherwise, $$ S_E(r) = S_E(c) = S_E(a) \cup S_E(b) \text{,} $$ $$ S_V(r) = S_V(a) \text{,} $$ $$ S_V(c) = S_V(a) \oplus S_V(b) \text{,} $$ where $\oplus$ denotes symmetric difference, i.e. $A \oplus B = (A \cup B) \setminus (A \cap B)$. Define the distance between two vertices in $T$ as the number of edges on the unique simple path between them. You are given a scoring parameter $M$ and $q$ queries. Each query gives a vertex $u$ on the tree and a non-negative integer $d$. Let the vertex set $X$ be the set of all vertices in $T$ whose distance to $u$ is at most $d$. Let the edge set $Y = \{ (a, b) \in E \hspace{3mu}\vert\hspace{3mu} a, b \in X \}$ be the set of edges inside $X$. It can be proven that, starting from $\epsilon$ and all $\iota(e)$ ($e \in E$), it is always possible to obtain an information $o \ne \bot$ with $S_E(o) = Y$ using finitely many calls to $R$ and $C$. For each query, you need to construct such an information $o$ under the constraint that the total number of calls to $R$ and $C$ is at most $M$. In particular, if $d = 0$, you may directly return the identity element $\epsilon$. ---- **[Implementation Details]** Please make sure your program starts with `#include "count.h"`. The header file `count.h` implements the following: 1. Defines the data type `info` corresponding to information. 2. Defines the `info` constant `emptyinfo` corresponding to $\epsilon$, which you may directly use in your program. 3. Defines and implements the following two merge functions, which you may directly call: ```cpp info MR(info a,info b); info MC(info a,info b); ``` - These two functions return the information corresponding to $R(a, b)$ and $C(a, b)$, respectively. **You must ensure that when calling $\boldsymbol{R(a, b)}$ and $\boldsymbol{C(a, b)}$, the result is not $\boldsymbol{\bot}$, otherwise the program may behave abnormally.** 4. Defines and implements a function to check whether an information is the identity element, which you may directly call: ```cpp bool isempty(info a); ``` - This function returns true if and only if $a$ is the identity element. You may refer to the reference interactive library for more implementation details. **You do not need to, and should not, implement `main()`.** You need to implement the following functions: ```cpp void init(int T, int n, int q, vector fa, vector e, int M); ``` - `T` is the test point id, `n` is the number of vertices, `q` is the number of queries, and `M` is the scoring parameter for this test point. - The lengths of `fa` and `e` are both $n - 1$. For $0 \le i < n - 1$, $fa[i]$ and $i + 2$ are the endpoints of the $i$-th edge $e_i$, and `e[i]` is the `info` element corresponding to $\iota(e_i)$ described above. The data guarantees that $fa[i]$ is less than $i + 2$. ```cpp info ask(int u, int d); ``` This gives a query; the meaning of the parameters is as described above. You need to return an information that satisfies the requirements at the end of the function. In the final test, for each test point, the interactive library will call `init` **exactly once**, and then call `ask` $q$ times. The interactive library uses a special implementation: a single variable of type `info` will always consume $12$ bytes of memory, **which is different from the provided reference interactive library**. To ensure the runtime memory usage stays within the limit, you need to make sure that there are not too many `info` variables existing simultaneously during execution. It is guaranteed that, under the call limit and without calling `isempty`, the final interactive library runs in at most 0.6 seconds, and the library itself uses at most 16 MiB of memory. It is also guaranteed that, when only executing ${10}^8$ calls to `isempty`, the final interactive library runs in at most 0.25 seconds. The provided files include `count.cpp` as a sample program, which contestants may continue implementing based on it. The provided files also include a backup file `count_backup.h`; we guarantee it is exactly the same as `count.h`. ---- **[How to Run the Test Program]** This problem directory provides two reference implementations of the interactive library, `grader.o` and `checker.o`, which are linkable files compiled from two different libraries. The interactive library used in the final test is different from these implementations, so your solution **must not depend on the specific implementation details of the library**, and also must not depend on the specific implementation of the `info` type in `count.h`. You need to modify the provided `count.h` to help with linking. Specifically, when linking `count.cpp` with `grader.o`, you need to comment out line 5 of `count.h` and keep line 4. Linking with `checker.o` is similar: you need to comment out line 4 and keep line 5. Contestants may modify the implementation of `count.h` to compile different programs. After modification, you can compile an executable in this directory using: ```bash 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 compiles `count.cpp` and links it with `grader.o` to produce `count`. The second command links it with `checker.o` to produce `count`. The executable `count` produced as above runs as follows: - It reads input from standard input in the following format: - The first line contains four integers $id, n, q, M$, which are the test point id, the number of vertices, the number of queries, and the scoring parameter. - The second line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$, which are the parent indices of vertices $2$ through $n$. When debugging locally, you need to ensure that for all $\forall i \in [2, n]$, $p_i < i$. - The next $q$ lines each contain two integers $u, d$, describing a query. - After reading, the interactive library will run the test. If your program does not satisfy the library constraints, it will output corresponding error messages. Otherwise, for the linked executable, it outputs: - One line with three integers $C_1, C_2, C_3$, where: - $C_1$ is the total number of interactive-library function calls made within `init`. - $C_2$ is the total number of interactive-library function calls made during the whole run. - $C_3$ is the maximum number of interactive-library function calls made within the $q$ calls to `ask`. - For these three statistics, we only count calls to `MR` and `MC`, and do not count calls to `isempty`. - When linking different files, the checks performed are different: - `grader.o`: it does not check whether the `info` returned by `ask` is correct, but it can help contestants determine whether the interaction operations meet the requirements. Its runtime is closest to the interactive library used in judging, so it can be used to test speed, but correctness is not guaranteed. - `checker.o`: it checks whether the `info` returned by `ask` is correct, and can also help contestants determine whether interaction operations meet the requirements. It also checks whether the `info` returned by `ask` is correct. This program can verify answer correctness. When debugging, you must ensure that the input to the executable `count` satisfies the format above; otherwise the output is not guaranteed to be correct.

See [How to Run the Test Program].

See [How to Run the Test Program].

Idea: zx2003, Solution: zx2003, Code: zx2003, Data: zx2003. **[Scoring]** In the final judging, **only** `count.cpp` will be collected. Modifying other files in your directory will not affect the judging result. **Note:** - **An uninitialized variable of type `info` is not guaranteed to be `emptyinfo`.** - **Please do not try to access or modify member variables of `info`, otherwise it will be considered an attack on the interactive library.** - **Do not call `MR` or `MC` before `init` is called, otherwise undefined behavior may occur.** - **You may only access variables you define yourself and `info` variables returned by the interactive library; attempting to access other memory may cause compilation errors or runtime errors.** **This problem is first subject to the same limits as traditional problems**, for example, compilation errors will cause the whole problem to score 0 points, runtime errors, exceeding time limits, exceeding memory limits, etc. will cause corresponding test points to score 0 points, and so on. Besides the above conditions, within a test point, if the program makes illegal function calls or gives an incorrect answer in any query operation, that test point will score 0 points. Otherwise, let $C_1$ and $C_3$ be the number of interactive-library function calls in `init`, and the maximum number of interactive-library function calls among all $q$ calls to `ask`, respectively. If $C_1 \le 3 \cdot {10}^7$ and $C_3$ does not exceed the scoring parameter $M$ of that test point, you will receive the score for that test point; otherwise you will not. Note: when computing $C_1$ and $C_3$, only calls to `MR` and `MC` are counted, and calls to `isempty` are not counted. ---- **[Sample #1]** See `count/count1.in` and `count/count1.ans` in the attachments. ---- **[Sample #2]** See `count/count2.in` and `count/count2.ans` in the attachments. This sample satisfies the special property A in the Constraints. ---- **[Sample #3]** See `count/count3.in` and `count/count3.ans` in the attachments. This sample satisfies the special property B in the Constraints. ---- **[Sample #4]** See `count/count4.in` and `count/count4.ans` in the attachments. ---- **[Constraints]** For all test points, $1 \le n \le 2 \times {10}^5$ and $1 \le q \le {10}^6$. In each query, $1 \le u \le n$ and $1 \le d \le n - 1$. | Test point | $n=$ | $q=$ | Special property | $M=$ | |:----------:|:-----------------:|:---------------:|:----------------:|:-----:| | $1$ | $1000$ | $10^4$ | | $500$ | | $2$ | $2000$ | $10^4$ | | $500$ | | $3,4$ | $10^5$ | $10^6$ | A | $5$ | | $5,6$ | $6 \times 10^4$ | $6\times 10^4$ | B | $50$ | | $7$ | $6 \times 10^4$ | $6 \times 10^4$ | B | $5$ | | $8$ | $10^5$ | $10^5$ | B | $5$ | | $9$ | $7500$ | $5 \times 10^4$ | C | $500$ | | $10$ | $10^4$ | $5 \times 10^4$ | | $500$ | | $11$ | $1.5 \times 10^4$ | $5 \times 10^4$ | | $500$ | | $12$ | $2 \times 10^4$ | $5 \times 10^4$ | | $50$ | | $13$ | $2.5 \times 10^4$ | $5 \times 10^4$ | | $5$ | | $14$ | $3 \times 10^4$ | $10^5$ | | $5$ | | $15$ | $6 \times 10^4$ | $10^6$ | D | $5$ | | $16$ | $6 \times 10^4$ | $10^6$ | | $5$ | | $17$ | $8 \times 10^4$ | $10^6$ | | $5$ | | $18$ | $10^5$ | $10^6$ | | $5$ | | $19$ | $1.5 \times 10^5$ | $10^6$ | | $5$ | | $20$ | $2 \times 10^5$ | $10^6$ | | $1$ | Special property A: guarantees that for all $\forall i \in [1, n - 1]$, the parent of vertex $i + 1$ is vertex $i$. Special property B: guarantees that all queries satisfy $u = 1$. Special property C: guarantees that all queries satisfy $d \le 100$. Special property D: guarantees that all queries satisfy $d \ge 1000$. Translated by ChatGPT 5