由于某些原因本题仅支持 C++ 各版本语言的提交。

\n

雅加达最大的主题公园中有 $N$ 个景点，它们从 $0$ 到 $N - 1$ 编号。这些景点由 $N - 1$ 条双向道路连接，任意两个景点间经由这些道路将存在唯一一条简单路径。道路从 $0$ 到 $N - 2$ 编号。第 $i$ 条道路连接第 $A_i$ 个景点与第 $B_i$ 个景点，经过这条道路需要花费一个小时。为了避免拥塞，每个景点将至多与三条道路相连。

\n

你想寻找一条游玩路线并使得每个景点都被参观一次。你认为从一个景点走到下一个景点时经过太多道路是十分无聊的。为了寻找一条有趣的路线，你打算安排景点的参观顺序，使得参观下一个景点所花费的时间不超过参观之前景点所花费的时间。换句话说，你想找到一个序列 $P_0, P_1, \\ldots, P_{N-1}$ 使其包含 $0$ 到 $N - 1$ 中的所有整数恰好一次，并且从第 $P_i$ 个景点到达第 $P_{i+1}$ 个景点所需的时间不超过从第 $P_{i-1}$ 个景点到达第 $P_i$ 个景点所需的时间，其中 $0 \\lt i \\lt N - 1$。

\n

你手上没有景点的完整地图，因此你必须向信息中心进行若干次询问才能找到一条有趣路线。你最多能进行 $Q$ 次询问，每次询问需要提供两个参数 $X$ 和 $Y$，其中 $0 \\le X, Y \\lt N$。每次询问是以下任意一种：

\n

从第 $X$ 个景点到第 $Y$ 个景点需要花费多少个小时。特别地，若 $X = Y$ 则回答将是 $0$。

\n

有多少个景点 $Z$ 满足，当你想从第 $X$ 个景点到达第 $Z$ 个景点时一定会经过第 $Y$ 个景点。第 $Y$ 个景点将会被计算在内，特别地，若 $X = Y$ 则回答将是 $N$。

\n

实现细节

\n

你必须引用 fun.h 头文件。

\n

你必须实现 createFunTour 函数:

\n

분석

제출 결과

【APIO2020】有趣的旅途

정보

결과

개발

지원

소개

계정이 없으신가요?

로그인