Archaeologist（考古学家）

题目描述

有一支考古队正在探索一处遗迹。由于很多考古学家迟到了，所以较早到达的人会先进入遗迹。

遗迹中共有 $N$ 个房间，编号为 $0,1,\\ldots,N-1$。若干对房间之间由双向走廊直接相连。遗迹中没有环，并且从入口可以到达所有房间；入口直接连接到房间 $0$。

共有 $K$ 名考古学家。每名考古学家都会从房间 $0$ 出发。考古学家没有时间回头，也就是说，他不能沿着来时的走廊反向走回去。每名考古学家也不知道自己是第几个进入遗迹的人。

每个房间有一个照明等级。初始时，在第一名考古学家进入前，所有房间的照明等级都是 $0$。考古学家站在某个房间时，可以在离开前把当前房间的照明等级改成 $0$ 到 $L$ 之间的任意整数。这个照明等级会一直保留，直到之后某名考古学家再次修改它。

考古学家站在某个房间时：

• 知道自己当前所在房间的编号；
• 不能知道每条可走走廊通向哪个房间；
• 但可以看到每条可走走廊另一端房间的照明等级；
• 来时的走廊不允许再走，因此不会出现在可选择走廊中。

在下一名考古学家进入前，上一名考古学家一定已经到达了自己最终停下的房间。

请为所有考古学家设计策略，使得 $K$ 名考古学家结束探索后，遗迹中每个房间都至少被访问过一次。

实现要求

这是一道通信 / Grader 题。你不需要编写 main 函数，只需要实现下列函数：

void archaeologist(
    int N,
    int K,
    int L,
    std::vector<int> map,
    int lightlevel,
    std::vector<int> paths
);

参数含义如下：

• N：房间数量；
• K：考古学家数量；
• L：最大照明等级；
• map：长度为 $N$ 的数组，其中 map[0] = -1，对于 $i \ge 1$，房间 $i$ 与房间 map[i] 直接相连；
• lightlevel：当前房间 $0$ 的照明等级；
• paths：从当前房间 $0$ 出发、除来路外所有可走走廊另一端房间的照明等级。这个数组会被任意打乱。

每次调用 archaeologist 表示一名考古学家的完整行动过程。评测程序会按顺序调用该函数恰好 $K$ 次。

在 archaeologist 内部，可以调用下面两个由评测程序提供的函数。

void set_light(int level);

将当前房间的照明等级设置为 level。必须满足 $0 \le level \le L$。

std::pair<int, std::vector<int>> take_path(int corridor);

让当前考古学家沿第 corridor 条可走走廊前往相邻房间。返回值的第一项是到达的新房间编号，第二项是新房间中所有可继续前进走廊另一端房间的照明等级；这个数组同样会被任意打乱。

传给 take_path 的 corridor 是当前可见 paths 数组中的下标。如果当前在房间 $0$，它对应初始传入的 paths；如果已经调用过 take_path，则对应上一次 take_path 返回的路径数组。

注意：不同考古学家的调用可能在不同进程中完成，也不保证每次调用都在不同进程中完成。因此不要依赖上一次调用留下的全局变量状态。你的程序也不能提前结束进程，例如调用 exit()。

提交说明

你的代码需要包含头文件：

#include "archaeologist.h"

提交模板如下：

#include "archaeologist.h"
#include <bits/stdc++.h>
using namespace std;

void archaeologist(int N, int K, int L, vector<int> map, int lightlevel, vector<int> paths) {
    // 在这里实现策略
}

正式评测时，系统会自动提供 archaeologist.h 和 grader。你只需要提交实现了 archaeologist 函数的源代码。

本地测试说明

下发文件中提供了 attachments/ 目录，其中包含官方本地测试用文件。C++ 选手可以参考：

• archaeologist.h：接口头文件；
• archaeologist.cpp：选手需要实现的文件；
• stub.cpp：本地测试用 grader；
• compile_cpp.sh、run_cpp.sh：本地编译和运行脚本。

本地测试 grader 的输入格式见下文“本地测试输入格式”。正式评测使用的 grader 与本地测试 grader 不完全相同，但接口一致。

本地测试输入格式

第一行包含三个整数：

$$N,K,L$$

第二行包含 $N-1$ 个整数，第 $i$ 个整数表示 map[i]。其中 map[0] = -1 是隐含的，不在输入中给出。

若探索成功，本地 grader 最后一行会输出：

All rooms explored successfully

否则会输出：

Not all rooms were explored

数据范围与子任务

每个测试点的时间限制为 $12$ 秒，空间限制为 $1$ GiB。

对于所有测试点：

$$1 \le N \le 1000.$$

$K$ 等于叶子房间数量，即除来路外没有其它可走走廊的房间数量。

子任务	分值	$L$ 的限制	额外限制
1	6	$L=1$	对所有 $1 \le i < N$，map[i]=0
2	14	$L=N$	无
3	15	无特殊限制	map 构成一棵满二叉树
4	18	$L$ 等于房间 $0$ 到最远房间的走廊数	map 数组中除了 $-1$ 外没有只出现一次的值
5	47	无特殊限制	无

这里，房间 $x$ 到房间 $0$ 的距离是两者之间简单路径上的走廊数。最远房间是到房间 $0$ 距离最大的房间。

满二叉树指：所有叶子到房间 $0$ 的距离相同，并且每个非叶子房间除来路外恰好有两条可走走廊。

样例

本地测试输入：

7 4 2
0 0 1 1 2 2

一种成功策略执行完后，grader 最后一行会输出：

All rooms explored successfully

@下发文件