loj#P3360. 「PA 2019」Sonda

「PA 2019」Sonda

题目描述

题目译自 PA 2019 Runda 5 Sonda

这是一道交互题。

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

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

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

交互方式

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

#include "sonlib.h"

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

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

你需要实现主函数

int main()

样例

样例输入

4 4 0
1 2
2 3
3 1
2 4

样例交互过程

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