UOJ Logo Universal Online Judge

UOJ

#726. 【JOISC2022】飞机旅行

附件下载 统计

这是一道通信题。

JOI 共和国中有 $N$ 座机场,编号为 $0,1,\dots,N-1$。其中有 $N-1$ 条航线,编号为 $0,1,\dots,N-2$。

航线 $i$ $(0 \le i \le N-2)$ 双向连接机场 $U_i$ 和 $V_i$。保证从每座机场都能经过若干条航线到达任意其他机场。

Benjamin 准备在 JOI 共和国进行一次说走就走的旅行。

他从游乐园所在的机场出发,且想在旅行的最后一天到达温泉所在的机场。游乐园在机场 $x$,而温泉在机场 $y$。

然而 Benjamin 不知道任何航线的信息,所以他会和航空公司的一位工作人员 Ali 联系。Benjamin 想知道他从机场 $x$ 到机场 $y$ 所需要经过的航线条数的最小值。Ali 知道所有航线的信息,但弱小可怜又无助的 Benjamin 并不知道应该怎么规划路线。

  1. Ali 为每座机场设置了一个识别码。识别码是一个 $[0,2N+19]$ 内的整数。
  2. Benjamin 知道机场 $x$ 的识别码 $X$ 和机场 $y$ 的识别码 $Y$。
  3. Benjamin 向 Ali 发送了一封电子邮件。这封邮件是一个长度恰为 $20$ 的字符串,且仅由 $\texttt 0,\texttt 1$ 构成。
  4. Ali 给 Benjamin 写一封信。这封信包含一个长度为 $[1,300\,000]$ 中的整数的字符串,且仅由 $\texttt 0,\texttt 1$ 构成。

请写两个程序,分别实现工作人员 Ali 和旅行者 Benjamin 的策略。

注意,在第 $2$ 步中,Benjamin 得知识别码 $X,Y$ 但没有得知机场编号 $x,y$。

任务

本题仅支持符合 C++11 及以上标准的 C++ 语言。

你需要提交两份文件,分别为 Ali.cppBenjamin.cpp

Ali

第一份文件是 Ali.cpp。其中应该实现 Ali 的策略,即包含以下两个函数。且其应当使用预编译指令 #include 包含 Ali.h

void Init(int N, std::vector<int> U, std::vector<int> V);

这个函数实现了 Ali 设置识别码的过程。对于每组测试用例,这个函数将恰被调用一次。

  • 参数 $\texttt N$ 是 JOI 共和国的机场个数。
  • 参数 $\texttt U, \texttt V$ 是长度为 $N-1$ 的数组。表示 $\texttt{U[i]},\texttt{V[i]}$ 是第 $i$ 条航线连接的机场编号 $U_i,V_i$ $(0 \le i \le N-2)$。
std::string SendA(std::string S);

这个函数实现了 Ali 给 Benjamin 写信的过程。对于每组测试用例,这个函数将恰在调用 SendB(见下)后被调用一次。

  • 参数 $\texttt S$ 是一个长度为 $20$ 的字符串,表示 Benjamin 发给 Ali 的邮件。
  • 该函数返回一个长度为 $[1,300\,000]$ 中的整数的字符串,表示 Ali 写给 Benjamin 的信。否则你的答案会被判定为 Wrong Answer [5]
  • 返回值的每个字符都是 $\texttt 0$ 或 $\texttt 1$。否则你的答案会被判定为 Wrong Answer [6]

在每次对 Init 的调用中,你需要每座机场调用如下函数。总共调用 $N$ 次。

void SetID(int p, int value);
  • 参数 $\texttt p$ 表示 Ali 正在设置机场 $\texttt p$ 的识别码。满足 $0 \le \texttt p \le N-1$。否则你的答案会被判定为 Wrong Answer [1]
  • 参数 $\texttt{value}$ 表示 Ali 选定的识别码。满足 $0 \le \texttt{value} \le 2N+19$。否则你的答案会被判定为 Wrong Answer [2]
  • 不允许对于同一个 $\texttt p$ 调用多于一次 SetID。否则你的答案会被判定为 Wrong Answer [3]
  • Init 函数调用结束时,SetID 的调用次数应当恰为 $N$。否则你的答案会被判定为 Wrong Answer [4]

当对 SetID 的调用被判作 Wrong Answer 时,你的程序会立即被结束。

Benjamin

第二份文件是 Benjamin.cpp。其中应该实现 Benjamin 的策略,即包含以下两个函数。且其应当使用预编译指令 #include 包含 Benjamin.h

std::string SendB(int N, int X, int Y);

这个函数实现了 Benjamin 给 Ali 发电子邮件的过程。对于每组测试用例,这个函数将恰在调用 Init 后被调用一次。

  • 参数 $\texttt N$ 是 JOI 共和国的机场个数。
  • 参数 $\texttt X$ 是机场 $x$ 的识别码。
  • 参数 $\texttt Y$ 是机场 $y$ 的识别码。
  • 该函数返回一个长度为 $20$ 的字符串,表示 Benjamin 发给 Ali 的邮件。否则你的答案会被判定为 Wrong Answer [7]
  • 返回值的每个字符都是 $\texttt 0$ 或 $\texttt 1$。否则你的答案会被判定为 Wrong Answer [8]
int Answer(std::string T);

这个函数应当计算出 Benjamin 从机场 $x$ 到机场 $y$ 所需要经过的航线条数的最小值。对于每组测试用例,这个函数将恰在调用 SendA 后被调用一次。

  • 参数 $\texttt T$ 是一个长度为 $[1,300\,000]$ 中的整数的字符串,表示 Ali 写给 Benjamin 的信。
  • 这个函数应当返回从机场 $x$ 到机场 $y$ 所需要经过的航线条数的最小值。

提示

  • 你的程序可以实现其他函数以供内部使用,或者使用全局变量。提交的文件会和评分器一同编译,得到单独一个可执行文件。所有全局变量和内部函数应当在一个未使用过的命名空间内声明,以免与其他程序冲突。评测时,Ali 和 Benjamin 的策略会分为两个进程,无法共享全局变量。
  • 你的程序不得使用标准输入输出流,也不得以任何方式访问任何文件。然而,你可以输出调试信息到标准错误流。

评分方式

一组测试数据包含 $Q$ 个测试用例,编号为 $0,1,\dots,Q-1$。以下变量的值会在每组用例中给定。

  • JOI 共和国的机场个数 $N$。
  • 游乐园所在的机场编号 $x$。
  • 温泉所在的机场编号 $y$。
  • 航班信息 $(U_0,V_0),(U_1,V_1),\dots,(U_{N-2},V_{N-2})$。

对于每组测试用例,将调用函数 Init,SendB,SendA,Answer。你的程序应当以合法参数调用合适的函数,且返回合适的值。这些函数将按如下顺序调用。

  1. 对于 $k=0,1,\dots,Q-1$,第 $2-5$ 步会按顺序执行一次。
  2. 调用函数 Init
  3. 调用函数 SendB
  4. 调用函数 SendA
  5. 调用函数 Answer

当你的程序被判作 Wrong Answer 时,你的程序会立即被结束,且被视作未通过该组测试数据。

编译与测试运行

你可以从附件下载中下载样例评分器来测试你的程序。附件下载中也提供了你应当提交的程序的一个样例。

样例评分器即 grader.cpp。为了测试你的程序,将 grader.cpp,Ali.cpp,Benjamin.cpp,Ali.h,Benjamin.h 放置在同一个目录下,并执行如下命令来编译你的程序。

g++ -std=gnu++17 -O2 -o grader grader.cpp Ali.cpp Benjamin.cpp

若编译成功,将会生成一个可执行文件 $\texttt{grader}$。

请注意,实际使用的评分器与下发的样例评分器不同。样例评分器仅会有单个进程,从标准输入中读取输入数据并将结果输出到标准输出。

样例评分器输入格式

第一行,一个正整数 $Q$,表示这个测试数据包含 $Q$ 组测试用例。

对于每组测试用例:

第一行,三个整数 $N,x,y$,分别表示机场个数,游乐园与温泉所在的机场编号。

接下来 $N-1$ 行,其中第 $i+1$ $(0 \le i \le N-1)$ 行包含两个正整数 $U_i,V_i$,表示航线 $i$ 连接的机场编号。

样例评分器输出格式

如果你的程序被判定为 Wrong Answer [1-8],样例评分器将以 “$\texttt{Wrong Answer [1]}$” 的格式输出(不包含引号)。

否则,对于每组测试用例,其输出函数 $\texttt{Answer}$ 的返回值和 Ali 给 Benjamin 写的信的最大长度。样例评分器并不检查 $\texttt{Answer}$ 的返回值是否正确。如:

Scenario 0: Your Answer = 3
Scenario 1: Your Answer = 1
Scenario 2: Your Answer = 4
Scenario 3: Your Answer = 1
Scenario 4: Your Answer = 5
Accepted: Maximum Length = 24

如果你的程序属于多种 Wrong Answer,样例评分器只会输出其中一种。

此外,除非你的程序在第一组测试用例中就被判为 Wrong Answer,那么即使你的程序在之后的测试用例中被判为 Wrong Answer [1-8],样例评分器也会按如下方式输出中间的结果。

Scenario 0: Your Answer = 3
Scenario 1: Your Answer = 1
Scenario 2: Your Answer = 4
Wrong Answer [8]

样例一

input

1
4 0 2
0 1
1 2
2 3

explanation

这里有样例评分器的一个样例输入和对应的函数调用。其中,机场 $0,1,2,3$ 的识别码分别为 $12,21,25,27$。

Ali 的调用 Ali 的返回值 Benjamin 的调用 Benjamin 的返回值
Init(4,[0,1,2],[1,2,3]) $~$ $~$ $~$
SetID(0,12) $~$ $~$ $~$
SetID(1,21) $~$ $~$ $~$
SetID(2,25) $~$ $~$ $~$
SetID(3,27) $~$ $~$ $~$
$~$ $~$ SendB(12,25) "00000111110000011111"
SendA("00...11") "10" $~$ $~$
$~$ $~$ Answer("10") 2

在样例输入中,有 $N(=4)$ 座机场和 $3$ 条航线。

  • 一条连接机场 $0$ 和 $1$ 的航线。
  • 一条连接机场 $1$ 和 $2$ 的航线。
  • 一条连接机场 $2$ 和 $3$ 的航线。

由于 Benjamin 需要经过至少 $2$ 条航线才能从机场 $x(=0)$ 到机场 $y(=2)$,所以函数 Answer 应当返回 $2$。

注意函数 SendB 的参数不是机场编号 $(x,y)=(0,2)$,而是识别码 $(X,Y)=(12,25)$。

样例二

input

2
10 0 9
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
15 12 8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14

explanation

在这组数据中,有 $Q=2$ 组测试用例。

  • 对于第一组用例,$\texttt{Answer}$ 应当返回 $9$。
  • 对于第二组用例,$\texttt{Answer}$ 应当返回 $6$。

数据范围

对于所有数据,满足:

  • $1 \le Q \le 50$。
  • $2 \le N \le 10\,000$。
  • $0 \le U_i < V_i \le N-1$ $(0 \le i \le N-2)$。
  • $0 \le x \le N-1$。
  • $0 \le y \le N-1$。
  • $x \ne y$。
  • 从任意机场都能够经过若干条航线到达任意其他机场。
  • 对于每个机场,最多有 $3$ 条航线连接其与其他机场。

详细子任务附加限制及分值如下表所示:

子任务编号 附加限制 分值
$1$ $Q=1$ $15$
$2$ $Q\ge 2$ $85$

子任务 1 评分方式

如果你的程序在子任务 1 的任何用例中被判为 Wrong Answer,则你在该子任务的分数为 $0$。

如果你的程序正确回答了子任务 1 中的所有用例,你的分数将按如下方式计算。其中 $L_1$ 是 Ali 给 Benjamin 写的信的最大长度。

$L_1$ 的值 对应分数
$150\,001 \le L_1 \le 300\,000$ $7$
$20\,001 \le L_1 \le 150\,000$ $11$
$L_1 \le 20\,000$ $15$

子任务 2 评分方式

如果你的程序在子任务 2 的任何用例中被判为 Wrong Answer,则你在该子任务的分数为 $0$。

如果你的程序正确回答了子任务 2 中的所有用例,你的分数将按如下方式计算。其中 $L_2$ 是 Ali 给 Benjamin 写的信的最大长度。注意,若 $L_2 \ge 1\,401$,你在该子任务的分数即为 $0$。

$L_2$ 的值 对应分数
$1\,401 \le L_2 \le 300\,000$ $0$
$71 \le L_2 \le 1\,400$ $52 - 35 \times \log_{10}(\frac{L_2}{70})$(四舍五入到最近的整数)
$45 \le L_2 \le 70$ $87 - 0.5 \times L_2$(四舍五入到最近的整数)
$25 \le L_2 \le 44$ $109 - L_2$
$L_2 \le 24$ $85$

保证合法的交互过程中,评测库不会使用超过共 $\texttt{1s}$ 时间,分别不会使用超过 $\texttt{32MB}$ 空间。

时间限制:两份程序共 $\texttt{4s}$

空间限制:两份程序分别 $\texttt{512MB}$