P14429 [JOISC 2014] 汉字接龙 / Kanji Shiritori
题目描述
**本题是一道通信题，只支持 C++ 语言的提交。请不要使用 C++14 (GCC 9) 提交。**
-------------------
来自日本的国际友人 Anna 和 Bruno 将在他们的学校里参加一场汉字考试。Anna 和 Bruno 知道 $N$ 个汉字（编号 $0$ 到 $N-1$）以及 $M$ 个单词（编号 $0$ 到 $M-1$）。所有给出的单词均由他们所知道的汉字组成，其中单词 $i$ 的第一个字符是汉字 $A_i$，最后一个字符是汉字 $B_i$。所有单词均满足 $A_i \neq B_i$。此外，所有单词的 $(A_i, B_i)$ 均不相同，即 $i \neq j$ 时 $(A_i, B_i) \neq (A_j, B_j)$。此外，每个单词都有确定的书写所需时间 $C_i$。
考试中，将依次出现 $Q$ 道如下问题。
> 问题 $j$：请给出从汉字 $S_j$ 开始、到汉字 $T_j$ 结束的一条汉字接龙序列。
所有问题均满足 $S_j \neq T_j$。此外，所有问题的 $(S_j, T_j)$ 均不相同，即 $i \neq j$ 时总有 $(S_i, T_i) \neq (S_j, T_j)$。
一个汉字接龙，是指前一个单词的最后一个字符与后一个单词的第一个字符相同的单词序列。一个从汉字 $S_j$ 开始、到汉字 $T_j$ 结束的汉字接龙，是指第一个单词的第一个字符为汉字 $S_j$ 且最后一个单词的最后一个字符为汉字 $T_j$ 的汉字接龙。
虽然可能存在多条作为答案的汉字接龙，但由于考试时间很短，必须给出其中所需时间最短的一条（若有多条，给出任意一条即可）。书写汉字接龙所需的时间即为其中包含的所有单词的书写所需时间之和。
就在考试即将开始前，Bruno 突然忘记了单词 $U_0, U_1, \ldots, U_{K-1}$ 的书写所需时间 $C_{U_0}, C_{U_1}, \ldots, C_{U_{K-1}}$。这 $K$ 个单词的第一个字符恰好都是相同的。Anna 在开考后从 Bruno 那里得知了这件事，于是决定在考试中向 Bruno 传递信息。考试中，Anna 可以通过敲桌子的声音向 Bruno 发送 $0$ 或 $1$。Anna 希望发送 $0$ 或 $1$ 的次数尽可能少。
为了帮助 Bruno 在考试中取得满分，请编写 Anna 向 Bruno 发送信息、Bruno 回答问题的程序。
### 实现细节
您需要以相同的编程语言提交两个文件。但是洛谷不能提交两个文件，所以您需要将两个文件合二为一提交。
------------------------
第一个文件是 `Anna.cpp`。该文件实现 Anna 的策略。您必须在开头 ~~引入头文件 `Annalib.h`~~ 声明函数 `int Tap(int x);`。同时，您必须实现以下函数：
```cpp
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[])
```
该函数仅在最初被调用一次。
- 参数 `N` 是汉字数量 $N$。
- 参数 `M` 是单词数量 $M$。
- 参数 `A` 是长度为 $M$ 的数组，元素 `A[i]` 是单词 $i$ 的第一个字符的编号 $A_i$。
- 参数 `B` 是长度为 $M$ 的数组，元素 `B[i]` 是单词 $i$ 的最后一个字符的编号 $B_i$。
- 参数 `C` 是长度为 $M$ 的数组，元素 `C[i]` 是单词 $i$ 的书写所需时间 $C_i$。
- 参数 `Q` 是问题数量 $Q$。
- 参数 `S` 是长度为 $Q$ 的数组，元素 `S[j]` 是问题 $j$ 的答案的第一个字符的编号 $S_j$。
- 参数 `T` 是长度为 $Q$ 的数组，元素 `T[j]` 是问题 $j$ 的答案的最后一个字符的编号 $T_j$。
- 参数 `K` 是 Bruno 忘记书写所需时间的单词数量 $K$。
- 参数 `U` 是长度为 $K$ 的数组，元素 `U[0], U[1], ..., U[K-1]` 是 Bruno 忘记书写所需时间的单词编号 $U_0, U_1, \ldots, U_{K-1}$。
在程序中，您可以调用以下函数以向 Bruno 传递信息：
```cpp
void Tap(int x)
```
- 参数 `x` 是 $0$ 或 $1$，表示向 Bruno 发送的信息，若不满足，则判定为 **Wrong Answer [1]**。
- 若 `Tap` 的调用次数超过了 $1000$，则判定为 **Wrong Answer [2]**。
若对 `Tap` 的调用被判定为 **Wrong Answer**，程序在该时即刻终止。
--------------
第二个文件是 `Bruno.cpp`。该文件实现 Bruno 的策略。您必须在开头 ~~引入头文件 `Brunolib.h`~~ 声明函数 `int Answer(int w);`。同时，您必须实现以下函数：
```cpp
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[])
```
该函数在 `Anna` 被调用后仅被调用一次。
- 参数 `N, M, A, B, Q, S, T, K, U` 的意思与 `Anna` 中的相同。
- 参数 `C` 是长度为 $M$ 的数组，元素 `C[i]` 是单词 $i$ 的书写所需时间 $C_i$。但是，若 $i$ 是 $U_0, U_1, \ldots, U_{K-1}$ 中的某一个，则值为 $-1$。
- 参数 `L` 是 Anna 发送的 $0$ 或 $1$ 的个数。
- 参数 `X` 是长度为 $L$ 的数组，表示 Anna 按 `X[0], X[1], ..., X[L-1]` 的顺序发送了 $0$ 或 $1$。
在程序中，您可以调用以下函数以向评分程序报告答案：
```cpp
void Answer(int w)
```
- 参数 `w` 是在 $[-1, M - 1] \cap \Z$ 中的一个数，表示 Bruno 对考试题目的回答。若不满足，判定为 **Wrong Answer [3]**。
- 对 `Answer` 的调用中应以问题的编号顺序依次包含 $Q$ 个问题的答案。具体地，对于第 $j~(0 \le j \le Q - 1)$ 个问题的答案，您的程序应这样回答：
- 对问题 $j$ 的答案的单词序列，从序列的第一个单词开始到最后一个单词，依次以单词编号为参数进行 `Answer` 的调用；
- 之后，调用 `Answer(-1)`。
- 对 `Answer` 的调用中若存在第 $Q$ 个 `Answer(-1)`，但其不是最后一次调用，判定为 **Wrong Answer [4]**。
- 对 `Answer` 的调用中若不存在第 $Q$ 个 `Answer(-1)`，则判定为 **Wrong Answer [5]**。
- 某个问题的答案序列长度为 $0$ 时，判定为 **Wrong Answer [6]**。
- 某个问题的答案中，某个单词的最后一个字符与下一个单词的第一个字符不同时，判定为 **Wrong Answer [7]**。
- 某个问题 $j$ 的答案中，第一个单词的第一个字符不是 $S_j$，或最后一个单词的最后一个字符不是 $T_j$ 时，判定为 **Wrong Answer [8]**。
- 某个问题的答案的书写所需时间不是最短时，判定为 **Wrong Answer [9]**。
------------------------
程序的内部实现中可以自由声明其他函数或全局变量。评分时，这两个程序将作为两个独立的进程运行，因此 Anna 侧和 Bruno 侧的程序全局变量无法共享。
您的提交不得通过标准输入输出或其他文件进行任何交互。
### 编译与执行方法
用于测试所编写程序的评分程序样例与 `Anna.cpp` 和 `Bruno.cpp` 的样例可以从附件中下载。您可以借助它们来编写程序。
评分程序样例由单个文件组成。该文件是 `grader.cpp`。测试所编写的程序时，请执行以下命令：
```bash
g++ -O2 grader.cpp Anna.cpp Bruno.cpp -o grader
```
编译成功后，将生成名为 `grader` 的可执行文件。
请注意，实际的评分程序与评分程序样例不同。评分程序样例从标准输入读取输入，向标准输出输出结果。
输入格式
评分程序样例从标准输入读取以下输入：
- 第 $1$ 行包含以空格分隔的整数 $N, M, Q, K$，表示汉字数量为 $N$，单词数量为 $M$，问题数量为 $Q$，Bruno 忘记书写所需时间的单词数量为 $K$。
- 接下来的 $M$ 行中，第 $i+1$ 行（$0 \le i < M$）包含以空格分隔的整数 $A_i, B_i, C_i$，表示单词 $i$ 的第一个字符为汉字 $A_i$，最后一个字符为汉字 $B_i$，书写所需时间为 $C_i$。
- 接下来的 $Q$ 行中，第 $j+1$ 行（$0 \le j < Q$）包含以空格分隔的整数 $S_j, T_j, Z_j$，表示问题 $j$ 的答案的第一个字符为汉字 $S_j$，最后一个字符为汉字 $T_j$，最短书写所需时间为 $Z_j$。
- 接下来的 $K$ 行中，第 $k+1$ 行（$0 \le k < K$）包含整数 $U_k$，表示 Bruno 忘记书写所需时间的单词为 $U_0, U_1, \ldots, U_{K-1}$。
输出格式
程序正常结束时，评分程序样例将在标准输出中输出一行以下信息：
- 正确的情况下，输出 `Accepted : L = x`，其中 `x` 表示 `Tap` 的调用次数。
- 错误的情况下，输出 `Wrong Answer [1]` etc.，表示错误类型。
说明/提示
#### 样例解释 1
一种可能的函数调用如下：
| Anna 侧 | Bruno 侧 |
|---------|---------|
| `Anna` | |
| `Tap(0)` | |
| `Tap(0)` | |
| `Tap(1)` | |
| `Tap(0)` | |
| | `Bruno` |
| | `Answer(4)` |
| | `Answer(-1)` |
| | `Answer(2)` |
| | `Answer(-1)` |
| | `Answer(1)` |
| | `Answer(0)` |
| | `Answer(-1)` |
请注意，此示例中函数的调用不一定有意义。
向 `Anna` 与 `Bruno` 传递的参数如下：
| 参数 | `Anna` | `Bruno` |
|-----|-----------|------------|
| `N` | $4$ | $4$ |
| `M` | $5$ | $5$ |
| `A` | $\{2, 0, 3, 0, 3\}$ | $\{2, 0, 3, 0, 3\}$ |
| `B` | $\{1, 2, 1, 1, 0\}$ | $\{1, 2, 1, 1, 0\}$ |
| `C` | $\{10, 20, 30, 40, 50\}$ | $\{10, -1, 30, -1, 50\}$ |
| `Q` | $3$ | $3$ |
| `S` | $\{3, 3, 0\}$ | $\{3, 3, 0\}$ |
| `T` | $\{0, 1, 1\}$ | $\{0, 1, 1\}$ |
| `K` | $2$ | $2$ |
| `U` | $\{1, 3\}$ | $\{1, 3\}$ |
| `L` | — | $4$ |
| `X` | — | $\{0, 0, 1, 0\}$ |
#### 数据范围与限制
**本题采用捆绑测试**。
- Subtask 0（10 points）：$Q \le 10$，每个问题均存在单词数量不超过 $10$ 的答案，`Tap` 的调用次数不超过 $1000$。
- Subtask 1（90 points）：设该子任务的测试数据中 `Tap` 的最大调用次数为 $L$。
- 若 $L \leq 64$，您获得 $90$ 分；
- 若 $64 < L \leq 90$，您获得 $\left\lfloor \left(\frac{90 - L}{90 - 64}\right)^2 \times 20 \right\rfloor + 70$ 分；
- 若 $90 < L \leq 160$，您获得 $30$ 分；
- 若 $160 < L \leq 180$，您获得 $22$ 分；
- 若 $L > 180$，您获得 $0$ 分。
对于所有测试数据，保证：
- $2 \le N \le 300$，$1 \le M \le N \times (N - 1)$，$0 \le A_i < N$，$0 \le B_i < N$，$A_i \neq B_i$，$(A_i, B_i) \neq (A_j, B_j)\ (i \neq j)$，$1 \le C_i \le 10^{16}\ (0 \le i \leq j < M)$；
- $1 \le Q \le 60$，$0 \le S_i < N$，$0 \le T_i < N$，$S_i \neq T_i$，$(S_i, T_i) \neq (S_j, T_j)$，从汉字 $S_i$ 到汉字 $T_i$ 的汉字接龙存在$\ (0 \le i \leq j < Q)$；
- $1 \le K \le 5$，$0 \le U_k < M\ (0 \le k < K)$，$U_i \neq U_j\ (0 \le i < j < K)$；
- Bruno 忘记的单词的第一个字符相同，即 $A_{U_0} = A_{U_1} = \cdots = A_{U_{K-1}}$。