Public Judge

pjudge

Time Limit: 1 s Memory Limit: 256 MB Communication

# 21635. 【PER #2】情报传递

Statistics

这是一道通信题

P 国的国土可被视为一张 $N$ 个点 $N-1$ 条边的无向连通图,其中第 $i$ ($0 \leq i \leq N-2$) 条边连接了顶点 $A_i$ 与 $B_i$。顶点的编号均为 $1 \sim N$ 中的正整数。

Pre-SDOI Training Camp(也被称作 Public Easy Round #2) 即将在 P 国举办,作为一名外国考生,你想要提前得知考试的地点,并希望在考试情报公布前潜入考试地点。为了提前得知考试情报,你已经联系了来自 P 国的一名内鬼,他通过情报网络得知了考试的举办地点已被安排在了顶点 $T$。由于 P 国的道路信息与考试地点属于机密信息,他无法将这些情报发送给你,于是他决定在每个顶点 $i$ ($1 \leq i \leq N$) 上放置一个告示牌,并在上面标记一个非负整数 $X_i$。

随后,你可以通过搭乘 P 国的交通工具到达 P 国的一个顶点 $S$,但是由于你与内鬼事先都不了解 P 国的交通信息,因此在你真正到达前,内鬼无法得知 $S$ 的值。当你位于一个点时,你可以得到以下信息:

  • 你当前所在的顶点的编号 $S$
  • 你当前所在的顶点上所标记的数字 $F$
  • 与你当前所在的顶点相邻的顶点数量 $L$
  • 与你当前所在的顶点相邻的顶点的编号 $P_0,P_1, \cdots, P_{L-1}$
  • 与你当前所在的顶点相邻的顶点上所标记的数字 $Q_0,Q_1, \cdots, Q_{L-1}$

你想要通过这些信息,得知你是否已经到达顶点 $T$。如果没有,那么你下一步应该前往哪一个顶点,使得该顶点恰好在 $S$ 与 $T$ 所构成的唯一简单路径上。

为了避免内鬼被发现,你们双方想要制定一个策略,使得内鬼所标记的数字尽可能小。

实现细节

这是一道通信题,本题仅支持 C++ 语言。

你需要提交两个程序,分别为 SpyParticipant,来实现你们双方的策略。

Spy

你需要提交的程序名为 Spy.cpp,描述内鬼传递信息的过程。

你需要包含头文件 Spy.h,并实现以下函数:

std::vector <int> Init(int N, int T, std::vector <int> A, std::vector <int> B)
  • 在每个测试点中,该函数会被调用恰好一次。
  • $\texttt{N}$ 表示 P 国的顶点数量 $N$。
  • $\texttt{T}$ 表示比赛举办地点的顶点编号 $T$。
  • $\texttt{A}$ 是一个长度为 $N-1$ 的数组 $A_0, A_1, \cdots, A_{N-2}$。
  • $\texttt{B}$ 是一个长度为 $N-1$ 的数组 $B_0, B_1, \cdots, B_{N-2}$。
  • 该函数需要返回一个长度恰好为 $N$ 的数组 $X_0,X_1,\cdots,X_{N-1}$,其中 $X_i$ 描述内鬼给点 $i+1$ 赋予的数字。
    • 你需要保证 $X_i \geq 0$。

Participant

你需要提交的程序名为 Participant.cpp,描述你的策略。

你需要包含头文件 Participant.h,并实现以下函数:

int Query(int S, int F, int L, std::vector <int> P, std::vector <int> Q)
  • 在每个测试点中,该函数会被调用恰好一次。
  • $\texttt{S}$ 表示你此时所在的顶点编号 $S$。
  • $\texttt{F}$ 表示顶点 $S$ 上的数字 $F$。
  • $\texttt{L}$ 表示顶点 $S$ 的度数 $L$。
  • $\texttt{P}$ 是一个长度为 $N-1$ 的数组 $P_0, P_1, \cdots, P_{L-1}$,表示 $S$ 的所有邻居。
  • $\texttt{Q}$ 是一个长度为 $N-1$ 的数组 $Q_0, Q_1, \cdots, Q_{L-1}$,其中第 $i$ ($0 \leq i \leq L-1$) 个数表示顶点 $P_i$ 上的数字。

该函数需要返回答案,具体地:

  • 如果顶点 $S$ 即为比赛举办地点(即 $S = T$),则需要返回 $S$。
  • 否则,返回一个顶点编号 $x \in \{ P_0,P_1,\cdots,P_{L-1} \}$,表示应从当前顶点前往顶点 $x$。
    • 容易发现,这样的顶点 $x$ 是唯一的。

样例交互库

下发文件中包含了样例交互库 grader.cpp,该交互库可以帮助你理解这道题目的题意并测试你的程序。在最终评测时,所使用的交互库与该样例交互库有所不同,你的程序不应依赖该样例交互库的实现。

你可以使用以下命令编译出可执行文件 answer

g++ grader.cpp Spy.cpp Participant.cpp -o answer -O2

可执行文件 answer 将从标准输入中读入以下格式的输入数据:

  • 输入的第一行包含三个整数 $N,S,T$。
  • 接下来 $N-1$ 行,每行两个整数 $A_i, B_i$。

可执行文件将向标准输出中输出以下信息:

  • 输出的第一行包含一个整数 $Y$,表示函数 Participant 的返回值。
  • 输出的第二行包含一个整数 $m$,表示函数 Spy 所返回的数组中所有元素的最大值。

请注意,样例交互库不会对你的程序的正确性做任何检查,即样例交互库不会检查你是否共用了全局变量,也不会检查你的程序所返回的值是否正确。

样例 1

考虑以下对样例交互库的输入数据:

5 3 2
1 3
3 2
3 4
4 5

以下是一种可能的通信过程:

# Spy Participant Grader
1 $ $ $ $ Call Spy(...)
2 Returned $\{0, 1, 1, 3, 1\}$ $ $ $ $
3 $ $ $ $ Call Participant(...)
4 $ $ Returned $2$ $ $

可执行文件向标准输出中输出

2
3

子任务

对于所有数据,$2 \leq N \leq 10^5$,$1 \leq S,T \leq N$,$1 \leq A_i, B_i \leq N$,保证给定的图联通。

在每个测试点中,如果你的程序超出了时间限制、超出了空间限制、发生了运行时错误,或最终输出的 $Y$ 的值不正确,则你获得 $0$ 分。

否则,设该测试点的满分为 $W$,你的得分与 $m$ 的值有关:

  • 若 $0 \leq m \leq 1$,则你的得分为 $W$。
  • 若 $2 \leq m \leq 4$,则你的得分为 $\dfrac{W}{\alpha^m}$。
  • 若 $5 \leq m \leq 10$,则你的得分为 $\dfrac{W}{\beta^m}$。
  • 若 $10 < m \leq 10^5$,则你的得分为 $\dfrac{W}{\beta^{25}}$。
  • 否则,你的得分为 $0$。
  • 其中 $\alpha = \frac{3}{2}, \beta = \frac{7}{4}$

本题中 $W=100$,你可以通过该得点分布表来参考不同的 $m$ 所对应的得点。

$m$ 得点
$1$ $100.000000$
$2$ $44.444444$
$3$ $29.629630$
$4$ $19.753086$
$5$ $6.092699$
$6$ $3.481543$
$7$ $1.989453$
$8$ $1.136830$
$9$ $0.649617$
$10$ $0.371210$
$11 \sim 10^5$ $0.000084$