Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100 Communication

# 21660. 【PR #6】情报传递 2

Statistics

这是一道通信题。

P 国的国土可被视为一张 $N$ 个点 $M$ 条边的有向图,其中第 $i$ ($0 \leq i \leq M-1$) 条边的起点为 $U_i$,终点 $V_i$,长度为 $W_i$。顶点的编号均为 $0 \sim N - 1$ 中的正整数。

【PER #2】情报传递中,你(Participant)通过内鬼的指引,成功得到了 Public Easy Round #2 的比赛地点。为了避免类似的情况再次发生,P 国下令决定下一场比赛的比赛流程将分为 $Q$ 天。对于每个 $0 \leq i \leq Q-1$,第 $i$ 场考试将要求所有考生必须统一到达顶点 $S_i$ 处,随后才能够前往考试地点 $T_i$。

你已经提前得知了 P 国的地图与接下来 $Q$ 场考试的 $S_0,S_1,\cdots, S_{Q-1}$ 与 $T_0, T_1, \cdots, T_{Q-1}$。你希望对每个 $0 \leq i \leq Q-1$,计算出从顶点 $S_i$ 道顶点 $T_i$ 的最短路径,以备规划考试时的行走路线。

不幸的是,由于通信传输的故障,你所得到的地图中,有恰好 $K$ 条边 $E_0,E_1,\cdots, E_{K-1}$ 的长度发送失败了。好在你发现,这些发送失败的边的起点均相同,即 $U_{E_0},U_{E_1},U_{E_2},\cdots,U_{E_{K-1}}$ 的值均相等。

你通过随身携带的通讯设备,向内鬼 Spy 发送了你丢失长度的边的编号 $E_0,E_1,\cdots, E_{K-1}$。随后,内鬼 Spy 可以向你发送一个长度不超过 $1\,000$ 的 0/1 串,你需要根据这些信息,求出每个 $S_i$ 到 $T_i$ 的最短路径。

实现细节

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

你需要提交两个程序,其中程序 Spy 描述内鬼向你发送信息的策略,程序 Participant 描述你的策略。

Spy

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

std::string SpySolve(int N, int M, int Q, int K, std::vector <int> U, std::vector <int> V, std::vector <long long> W, 
                            std::vector <int> S, std::vector <int> T, std::vector <int> E);
  • 在每个测试点中,该函数会被调用恰好一次。
  • 参数 $\texttt{N}$ 表示顶点的数量 $N$。
  • 参数 $\texttt{M}$ 表示有向边的数量 $M$。
  • 参数 $\texttt{Q}$ 表示比赛的天数 $Q$。
  • 参数 $\texttt{K}$ 表示丢失长度的边的数量 $K$。
  • 参数 $\texttt{U}$ 为一个长为 $M$ 的数组 $U_0,U_1,\cdots, U_{M-1}$,描述每条边的起点。
  • 参数 $\texttt{V}$ 为一个长为 $M$ 的数组 $V_0,V_1,\cdots, V_{M-1}$,描述每条边的终点。
  • 参数 $\texttt{W}$ 为一个长为 $M$ 的数组 $W_0,W_1,\cdots, W_{M-1}$,描述每条边的长度。
  • 参数 $\texttt{S}$ 为一个长为 $Q$ 的数组 $S_0,S_1,\cdots, S_{Q-1}$,描述每组询问的起点。
  • 参数 $\texttt{T}$ 为一个长为 $Q$ 的数组 $T_0,T_1,\cdots, T_{Q-1}$,描述每组询问的终点。
  • 参数 $\texttt{E}$ 为一个长为 $K$ 的数组 $E_0,E_1,\cdots, E_{K-1}$,描述被丢失的边的编号。
  • 你需要返回一个仅包含 01 的字符串 $Z$,描述 Spy 需要发送给 Participant 的信息。

Participant

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

void ParticipantSolve(int N, int M, int Q, int K, std::vector <int> U, std::vector <int> V, std::vector <long long> W, 
                            std::vector <int> S, std::vector <int> T, std::vector <int> E, std::string Z);
  • 在每个测试点中,该函数会被调用恰好一次。
  • 参数 $\texttt{N}$ 表示顶点的数量 $N$。
  • 参数 $\texttt{M}$ 表示有向边的数量 $M$。
  • 参数 $\texttt{Q}$ 表示比赛的天数 $Q$。
  • 参数 $\texttt{K}$ 表示丢失长度的边的数量 $K$。
  • 参数 $\texttt{U}$ 为一个长为 $M$ 的数组 $U_0,U_1,\cdots, U_{M-1}$,描述每条边的起点。
  • 参数 $\texttt{V}$ 为一个长为 $M$ 的数组 $V_0,V_1,\cdots, V_{M-1}$,描述每条边的终点。
  • 参数 $\texttt{W}$ 为一个长为 $M$ 的数组 $W_0,W_1,\cdots, W_{M-1}$,描述每条边的长度。特别地,对于所有 $0 \leq i \leq K-1$,都有 $W_{E_i} = -1$,表示这些边的长度信息已经丢失。
  • 参数 $\texttt{S}$ 为一个长为 $Q$ 的数组 $S_0,S_1,\cdots, S_{Q-1}$,描述每组询问的起点。
  • 参数 $\texttt{T}$ 为一个长为 $Q$ 的数组 $T_0,T_1,\cdots, T_{Q-1}$,描述每组询问的终点。
  • 参数 $\texttt{E}$ 为一个长为 $K$ 的数组 $E_0,E_1,\cdots, E_{K-1}$,描述被丢失的边的编号。
  • 参数 $\texttt{Z}$ 表示 Spy 发送给 Participant 的 0/1 串 $Z$。

你需要调用以下函数恰好 $Q$ 次:

void Report(std::vector<int> P);
  • 在每个测试点中,你需要调用该函数恰好 $Q$ 次。
  • 对于第 $i$ 次调用($0 \leq i < Q$),参数 $P$ 需要描述第 $i$ 组询问的最短路径。
  • 设 $P$ 的长度为 $L$,则你需要保证 $A_{P_0} = S_i, B_{P_{L-1}}=T_i$,且对任意 $0 \leq k \leq L-2$,都有 $B_{P_k}=A_{P_{k+1}}$。
  • 换句话说,$P$ 按顺序描述了路径上每条边的编号。
  • 你可以提交任意一组合法的最短路径。

样例交互库

本题下发文件中含有样例交互库 grader.cpp,选手可使用以下命令编译得到可执行文件:

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

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

  • 输入的第一行包含四个整数 $N, M, Q, K$。
  • 接下来 $M$ 行,每行三个整数 $U_i, V_i, W_i$。
  • 接下来 $Q$ 行,每行两个整数 $S_i, T_i$。
  • 接下来 $K$ 行,每行一个整数 $E_i$。

可执行文件将向标准输出中输出以下数据:

  • 若通信过程出现了错误,则输出对应的错误信息。
  • 否则,输出将包含恰好 $Q$ 行。
  • 每行首先包含一个整数 $k$,表示路径的长度。
  • 接下来 $k$ 个整数,描述路径。

需要注意的是,样例交互库并不会检查你的答案是否正确。为了提高大家的参赛体验,在下发文件中提供了样例校验器 checker.cpp。选手可以使用以下命令编译得到可执行文件 checker

g++ checker.cpp -o checker -O2 -std=c++14

随后,你可以使用以下命令来检查你的程序:

./checker <input-file> <output-file>

其中 input-file 为你想要检查的测试用例的输入文件,output-file 为你想要检查的测试用例的输出文件。

需要注意的是,在最终评测时,所使用的交互库与下发的样例交互库有所不同。特别地,程序 Spy 与 Participant 将分别编译并运行在两个不同的进程中,两个进程之间不能通过任何方式进行通信。选手程序不应该也不能从标准输入中读取任何信息,或向标准输出中输出任何信息,否则可能会产生不可预料的错误。

本题的时间限制与空间限制均指进程 Spy 与 Participant 各自的限制,即你需要保证两个进程均不超过时间限制(1.0 秒)与空间限制(512MB)。保证在最终使用的两个交互库中,每个交互库所消耗的时间均不超过 50ms,空间均不超过 8MB,即每个进程都至少有 950ms 的时间与 504MB 的空间可用。

样例数据

样例 1 输入

5 5 3 1
0 1 2
0 2 3
0 3 1
1 4 5
2 4 5
0 4 
1 4 
0 3 
1

样例 1 输出

2 0 3
1 3
1 2

样例 1 解释

本组数据中的有向图如下所示:

problem_21660_3.png

对于第一组询问,最优的路径为 $0 \stackrel{e_0}{\longrightarrow} 1 \stackrel{e_3}{\longrightarrow} 4$,路径的长度为 $7$。

对于第二组询问,最优的路径为 $1 \stackrel{e_3}{\longrightarrow} 4$,路径的长度为 $5$。

对于第三组询问,最优的路径为 $0 \stackrel{e_2}{\longrightarrow} 3$,路径的长度为 $1$。

故程序 Participant 应当依次调用以下函数:

  • Report({ 0, 3 });
  • Report({ 3 });
  • Report({ 2 });

样例 2 输入

6 7 4 3
0 1 2
0 2 4
0 5 3
1 3 3
1 4 2
2 1 1
4 2 1
0 3
0 4
4 3
2 1
0
1
2

样例 2 输出

2 0 3
2 0 4
3 6 5 3
1 5

子任务

对于 $100\%$ 的数据,$2 \leq N \leq 300$,$1 \leq M \leq N \times (N-1)$,$1 \leq Q \leq 60$,$1 \leq K \leq 5$,$0 \leq U_i, V_i, S_i, T_i \leq N - 1$,$1 \leq W_i \leq 10^{16}$,$0 \leq E_i \leq M-1$。

对于 $100\%$ 的数据,图中不存在重边与自环(即 $(A_i, B_i)$ 两两不同,且 $A_i \ne B_i$),不存在重复的询问(即 $(S_i, T_i)$ 两两不同),询问的起点与终点不同(即 $S_i \ne T_i$),且 $E_0, E_1, \cdots, E_{K-1}$ 两两不同。

对于 $100\%$ 的数据,保证从 $S_i$ 到 $T_i$ 至少有一条合法的路径,保证 $U_{E_0}=U_{E_1}=U_{E_2} = \cdots = U_{E_{K-1}}$。

设 $Y$ 表示 Spy 能够返回的 0/1 串的最长的长度,$L$ 表示你所返回的 0/1 串的长度。

子任务编号 $Q \leq $ $Y = $ 特殊性质 分值
$1$ $10$ $1\,000$ A 5
$2$ $60$ $180$ 95
  • 性质 A:保证存在一条从 $S_i$ 到 $T_i$ 的最短路径,使得所经过的边的数量不超过 $10$。

对于子任务 2,你的得分将于 $L$ 的值有关:

$L$ 分值
$180 < L$ $0$
$160 < L \leq 180$ $11$
$90 < L \leq 160$ $15 + \frac{2(160 - L)}{5}$
$64 < L \leq 90$ $43 + 52 \cdot \left(\frac{90-L}{90-64}\right)^2$
$L \leq 64$ $95$

problem_21660_scoring_2.png