#3360. 「PA 2019」Sonda

内存限制:256 MiB 时间限制:2000 ms 题目类型:交互
上传者: EntropyIncreaser

题目描述

题目译自 PA 2019 Runda 5 Sonda

这是一道交互题。

有一个 n 个点的无向连通图。你有一个探测器,它最初在 1 号节点。

你每次可以向探测器发送指令,给出节点 v ,如果当前节点和 v 之间有一条边,那么探测器就会移动到该节点,每次发出这一指令就会得到反馈信息。若探测器进行了移动并且这是探测器第偶数次移动,那么返回「成功」,否则返回「失败」。你最多可以发送 10^6 次该指令。

你还另外需要进行 n 次标记操作,需要保证恰好在机器人位于每个节点的时候进行一次标记操作。

交互方式

您的程序需要引用交互库:

#include "sonlib.h"

这个交互库提供以下函数:

int GetN()
  • 返回一个正整数 n(3\le n\le 400) ,表示这个图的节点数。
int GetSubtask()
  • 返回一个整数 s(0\le s\le 3) ,表示子任务类型。
    • s=0 ,则表示该图没有任何附加性质;
    • s=1 ,表示图为完整的二分图,即可以将点集划分为两非空集合 A,B ,每个点都属于 A B 中的一个,并且有 |A|\cdot |B| 条边;
    • s=2 ,保证图中 1 2 2 3 3 1 之间一定有边;
    • s=3 ,保证图中所有点恰好与两个点相连。
int MoveProbe(int v)
  • 向探测器发出「走向节点 v 」的指令,如果探测器当前就在节点 v ,你的程序会被直接判为错误。若探测器进行了移动并且这是探测器第偶数次移动,那么返回 1,否则返回 0,若探测器没有进行移动,也返回 0
void Examine()
  • 让探测器标记当前节点。如果该节点已经被标记,你的程序会被直接判为错误。当完成了所有节点的标记操作后,程序会被判定为正确并自动退出。

你需要实现主函数

int main()

样例

样例输入

4 4 0
1 2
2 3
3 1
2 4

样例交互过程

函数调用 返回值 当前探测器位置 成功移动次数 注释
\texttt{GetN()} 4 1 0 图中有 4 个点
\texttt{GetSubtask()} 0 1 0 参数 s=0
\texttt{Examine()} - 1 0 标记 1 号点
\texttt{MoveProbe(4)} 0 1 0 1 4 之间没有边
\texttt{MoveProbe(2)} 0 2 1 探测器从 1 移动到 2 ,此时探测器移动成功次数为奇数
\texttt{MoveProbe(3)} 1 3 2 此时探测器移动成功次数为偶数
\texttt{Examine()} - 3 2 标记 3 号点
\texttt{MoveProbe(2)} 0 2 3
\texttt{Examine()} - 2 3 标记 2 号点
\texttt{MoveProbe(4)} 1 4 4
\texttt{Examine()} - - - 探测器已将每个点都探测一次,因此程序结束,该用例通过