P14403 [JOISC 2016] 雪中的道路 / Snowy Roads【通信题暂无法评测】

俄罗斯许多地区在冬季会降雪。俄罗斯共有 $N$ 个城市，编号从 $0$ 到 $N-1$。俄罗斯有 $N-1$ 条道路，编号从 $0$ 到 $N-2$。道路 $i$（$0 \le i \le N-2$）连接两个不同的城市 $A_i$ 和 $B_i$（$0 \le A_i < B_i \le N-1$），且为双向通行。任意两个不同的城市之间，均可通过若干条道路相互到达。 各条道路的降雪状况会随日期变化。在任意一天内，每条道路的降雪状况要么是正在下雪，要么是没有下雪，且在一天之内不会发生变化。 Anya 和 Boris 在俄罗斯交通局工作。Anya 属于道路信息管理部门，Boris 属于负责回答市民咨询的部门。市民的咨询内容是：为了从俄罗斯首都（即城市 $0$）前往其他某个城市，至少需要经过多少条正在下雪的道路？Boris 通常在接到咨询后，会与 Anya 协调，再向市民回复。 这一次，俄罗斯将在 $Q$ 天内举办一场编程竞赛的世界大会。会议期间，通信线路预计将变得拥堵，Anya 和 Boris 将难以直接沟通。为此，Anya 和 Boris 决定采用以下方式协作： - Anya 在每天开始时接收当天的降雪信息，并将数据发送至中继服务器。 - Boris 在收到市民咨询后，通过与中继服务器交互来获取信息并作出回复。 但 Anya 和 Boris 的协作方式存在以下限制： - 中继服务器的容量为 $L = 1000$ 比特。Anya 每天最多只能向中继服务器存储 $L$ 比特的信息。 - 存储在中继服务器中的数据在每天开始时会被全部初始化为 0。 - Boris 与中继服务器每次交互，只能读取指定的 1 比特信息。 - 为回答每个市民咨询，Boris 与中继服务器交互的次数最多为 20 次。 你作为交通局局长的顾问，需要为 Anya 和 Boris 设计一套策略。 :::align{center}  将“中継サーバ”改为“中继服务器”，“$L$ ビット”改为“$L$ 比特”，“質問ごとに20ビットまで”改为“每个问题最多 $20$ 比特”，“降雪情報”改为“降雪信息”。 ::: **题目** 请编写一个程序，实现 Anya 和 Boris 的策略，使其能够正确回答市民的咨询。 **实现细节** 你必须使用同一种编程语言提交两个文件。 第一个文件的文件名必须为 `Anya.c` 或 `Anya.cpp`。该文件用于实现 Anya 的策略，必须实现以下两个函数。程序需包含头文件 `Anyalib.h`。 - `void InitAnya(int N, int A[], int B[])` 此函数在每个测试用例中仅被调用一次。 - 参数 $N$ 表示城市的数量。 - 参数数组 $A[]$ 和 $B[]$ 均为长度为 $N-1$ 的数组，表示道路的连接信息。对于每个 $i$（$0 \le i \le N-2$），整数 $A[i]$ 和 $B[i]$ 表示道路 $i$ 双向连接城市 $A[i]$ 和 $B[i]$，并满足 $0 \le A[i] < B[i] \le N-1$。 - `void Anya(int C[])` 此函数在 `InitAnya` 被调用后，将被调用 $Q$ 次。该函数用于在每天开始更新道路降雪信息时，决定 Anya 应保存至中继服务器的比特序列。 - 参数 $C[]$ 是长度为 $N-1$ 的数组，表示道路的降雪信息。对于每个 $i$（$0 \le i \le N-2$），整数 $C[i]$ 表示道路 $i$ 的降雪状况：若 $C[i] = 1$，表示道路 $i$ 正在下雪；若 $C[i] = 0$，表示道路 $i$ 未下雪。 在函数 `Anya` 中，你可以调用以下函数： - `void Save(int place, int bit)` 该函数表示 Anya 向中继服务器写入比特的操作。 - 参数 `place` 表示写入比特的位置，其值必须为 $0$ 到 $L-1$ 之间的整数。若指定的值超出此范围，将被判为 **Wrong Answer [1]**。此外，在每次 `Anya` 函数调用中，对同一 `place` 的调用次数不得超过一次；若对同一位置调用超过一次，将被判为 **Wrong Answer [2]**。 - 参数 `bit` 表示要写入的比特值，必须为 $0$ 或 $1$。若指定的值不是 $0$ 或 $1$，将被判为 **Wrong Answer [3]**。 调用 `Save` 后，中继服务器第 `place` 位的值将被设置为 `bit`。 若 `Save` 的调用被判定为不正确，程序将在该时刻立即终止。 在函数 `Anya` 被调用之前，中继服务器的所有比特位必定已被初始化为 0。换言之，若函数 `Save` 未执行任何写入操作，则函数 `Anya` 结束时，所有位仍为 0。 第二个文件的文件名必须为 `Boris.c` 或 `Boris.cpp`。该文件用于实现 Boris 的策略，必须实现以下两个函数。程序需包含头文件 `Borislib.h`。 - `void InitBoris(int N, int A[], int B[])` 此函数在每个测试用例中仅被调用一次。 - 参数 $N$ 表示城市的数量。 - 参数数组 $A[]$ 和 $B[]$ 均为长度为 $N-1$ 的数组，表示道路的连接信息。对于每个 $i$（$0 \le i \le N-2$），整数 $A[i]$ 和 $B[i]$ 表示道路 $i$ 双向连接城市 $A[i]$ 和 $B[i]$，并满足 $0 \le A[i] < B[i] \le N-1$。 - `int Boris(int city)` 此函数在 `InitBoris` 被调用后，将被调用若干次。该函数用于响应市民的咨询。 - 参数 `city` 表示市民的咨询内容：`city` 是一个介于 $1$ 到 $N-1$ 之间的整数，表示从城市 $0$ 移动到城市 `city`，至少需要经过多少条正在下雪的道路。 - 函数 `Boris` 必须返回一个介于 $0$ 到 $N-1$ 之间的整数作为答案。若返回值超出此范围，将被判为 **Wrong Answer [4]**。若答案错误，将被判为 **Wrong Answer [7]**。 在函数 `Boris` 中，你可以调用以下函数： - `int Ask(int place)` 该函数表示 Boris 从中继服务器读取一个比特位的操作。 - 参数 `place` 表示要读取的比特位置，其值必须为 $0$ 到 $L-1$ 之间的整数。若指定的值超出此范围，将被判为 **Wrong Answer [5]**。 - 函数 `Ask` 的返回值为一个整数，表示中继服务器第 `place` 位的当前值，其值只能是 $0$ 或 $1$。 - 此外，在每次 `Boris` 函数调用中，`Ask` 函数最多只能被调用 20 次；若超过 20 次，将被判为 **Wrong Answer [6]**。 若 `Ask` 的调用被判定为不正确，程序将在该时刻立即终止。 **评分流程** 评分将按以下步骤进行。若程序在任意步骤中被判定为不正确，程序将在该时刻立即终止。 (1) 为提供道路信息，函数 `InitAnya` 和 `InitBoris` 将按顺序各被调用一次。 (2) 对于 $i = 1, \dots, Q$，依次执行以下操作：  (a) 调用函数 `Anya` 一次。这对应于第 $i$ 天开始时道路降雪信息更新后，Anya 决定向中继服务器保存的比特序列。  (b) 调用函数 `Boris` $D_i$ 次。其中 $D_i$ 表示第 $i$ 天市民咨询的次数。在第 $j$ 次调用（$1 \le j \le D_i$）中，传入的参数为 $R_{ij}$（$1 \le R_{ij} \le N-1$）。若第 $j$ 次调用 `Boris` 的返回值与从城市 $0$ 到城市 $R_{ij}$ 所需经过的下雪道路的最小数量不一致，则判定为不正确。 (3) 若程序在上述所有步骤中均未被判定为不正确，则判定为正确。 **重要注意事项** - 执行时间与内存使用量的测量对象仅为“评分流程”中的步骤 (1) 和 (2)。若程序被判定为正确，则在步骤 (2) 中，`Anya` 总共被调用 $Q$ 次，`Boris` 总共被调用 $D_1 + \cdots + D_Q$ 次。 - Anya 和 Boris 不得获知 $D_1, \dots, D_Q$ 的具体数值。 - 函数 `Boris` 不会被告知 Anya 在何时更新了中继服务器中的数据。 - 为内部使用，你可以在程序中实现其他函数或声明全局变量。但请注意，提交的两个程序将与评分程序链接为一个可执行文件，因此各文件内的全局变量和内部函数（除 `InitAnya`、`Anya`、`InitBoris`、`Boris` 外）必须声明为 `static`，以避免与其他文件发生冲突。评分时，程序将作为两个独立进程（Anya 侧和 Boris 侧）运行，因此 Anya 侧与 Boris 侧的程序不能共享全局变量。 - 你的提交必须使用标准输入/标准输出，或任何其他文件交互方式均不允许。 **编译与运行方法** 为测试你编写的程序，评分程序的样本已包含在可从竞赛网站下载的压缩包中。该压缩包内还包含必须提交的文件的样本。 评分程序的样本由一个文件构成，该文件名为 `grader.c` 或 `grader.cpp`。当你将编写的程序命名为 `Anya.c` 与 `Boris.c`，或 `Anya.cpp` 与 `Boris.cpp` 时，可通过执行以下命令测试程序： - **C 语言情况** ``` gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm ``` - **C++ 语言情况** ``` g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp ``` 若编译成功，将生成名为 `grader` 的可执行文件。 请注意，实际的评分程序与评分程序样本有所不同。评分程序样本以单个进程运行，该程序从标准输入读取数据，并将结果输出至标准输出。 **评分程序样本的概要** 评分程序样本将按照“评分流程”调用相关函数。请注意，以下行为与实际评分程序不同： - 评分程序样本不会执行 **Wrong Answer [7]** 的判定，而是直接输出针对每个咨询调用函数 `Boris` 的返回值。

评分程序样本从标准输入读取以下数据： - 第 1 行包含一个整数 $N$，表示城市数量为 $N$ 个。 - 接下来的 $N-1$ 行中，第 $i+1$ 行（$0 \le i \le N-2$）包含两个以空格分隔的整数 $A_i$ 和 $B_i$，表示道路 $i$ 双向连接城市 $A_i$ 和 $B_i$。 - 下一行包含一个整数 $Q$，表示大会将在 $Q$ 天内举办。 - 接下来的 $Q$ 行中，第 $i$ 行（$1 \le i \le Q$）包含一个长度为 $N-1$ 的字符串 $S_i$ 以及 $D_i + 1$ 个以空格分隔的整数。字符串 $S_i$ 表示第 $i$ 天的降雪信息：从左起第 $j+1$ 个字符（$0 \le j \le N-2$）若为 `1`，表示道路 $j$ 正在下雪；若为 `0`，表示道路 $j$ 未下雪。随后的 $D_i + 1$ 个整数中，第一个整数为 $D_i$，接下来的 $D_i$ 个整数 $R_{i1}, \dots, R_{iD_i}$ 表示第 $i$ 天的 $D_i$ 个咨询内容：第 $j$ 个咨询（$1 \le j \le D_i$）询问从城市 $0$ 到城市 $R_{ij}$ 所需经过的下雪道路的最小数量。

评分程序样本将向标准输出输出以下信息（引号在实际输出中不会出现）： - 若程序在运行过程中被判定为不正确，将输出不正确类型的标识，如 “**Wrong Answer [1]**”，随后程序终止。 - 在第 $i$ 次（$1 \le i \le Q$）调用 `Anya` 之后，若随后调用的 $D_i$ 次 `Boris` 均未被判定为不正确，则在该时刻输出一行，包含 $D_i$ 个以空格分隔的整数。其中第 $j$ 个整数（$1 \le j \le D_i$）为 `Boris(R_{ij})` 的返回值。 若运行中的程序同时满足多个不正确条件，输出的不正确类型仅为其中之一。

### 数据范围 所有输入数据均满足以下条件： - $2 \le N \le 500$。 - $1 \le Q \le 500$。 - $0 \le A_i < B_i \le N - 1$（$0 \le i \le N - 2$）。 - $1 \le D_j \le Q$（$1 \le j \le Q$）。 - $D_1 + \cdots + D_Q \le 500$。 - 任意两个不同的城市之间，总存在至少一条路径可以互相到达。 ### 子任务 **子任务 1 [15 分]** - 满足 $N \le 20$。 **子任务 2 [5 分]** - 满足 $N \le 100$。 **子任务 3 [35 分]** 需满足以下条件： - $A_i = i$（$0 \le i \le N - 2$）。 - $B_i = i + 1$（$0 \le i \le N - 2$）。 **子任务 4 [45 分]** 无额外限制。 翻译由 Qwen3-235B 完成