← 返回题目列表

AtCoder · joisp2025_f

F. 太空窃贼

中文机器翻译题面 查看原题

配点: 100 点

分发文件

如何使用AtCoder提交

使用 C++ 时 请包含

  • thief.h 并实现问题陈述中指定的功能。
  • 不要使用标准输入/输出或文件输入/输出。

使用其他语言时

  • 请按照问题文本的 JOIG 版本中的指定进行沟通。 如果执行

注意

  • 300 查询,则判断端和输入/输出最多消耗1200毫秒。
  • 由于测试用例数量较多,如果无法正确回答输入,我们建议尽早结束该过程。

你作为怪盗活跃在JOI星系。

在 JOI 星系 编号至 0 从 N - 1 有 N 颗星星。另外, 有0 从 M - 1 有 M 扭曲设备。扭曲装置 i (0 \leqq i \leqq M - 1) 是一颗星星 U_i 和星星 V_i 双向连接。其中 2 你可以使用一些扭曲装置在两颗恒星之间旅行。

JOI 银河系的一颗恒星上藏着一把钥匙,另一颗恒星上藏着一个宝箱。你的任务是找出钥匙和宝箱隐藏的星星编号。为此,请提出以下问题: 300 次。

  • 每个扭曲装置 i (0 \leqq i \leqq M - 1),星号 U_i 卡拉星 V_i 确保仅在一个方向将其系在星星上。 V_i 卡拉星 U_i 。
  • 然后,询问是否可以使用一些扭曲装置从有钥匙的星球移动到有宝箱的星球。

通过做题你会发现关键是隐藏星星的数量 A 是隐藏宝箱的星星的编号。 我想识别 B 。为了在任务中获得高评价,您需要问尽可能少的问题。

给定有关星系的信息,通过提问你可以找到隐藏钥匙的恒星的编号。 A 以及宝箱隐藏的星星编号。 编写一个程序来实现识别 B 的策略。


实施细节

你 1 您必须提交两个文件。

您提交的文件是 名称是 thief.cpp 。thief.cpp 表示 #include 通过预处理器指令 您必须阅读 thief.h 并实现以下功能。

  • void solve(int N, int M, std::vector<int> U, std::vector<int> V)
    • 此功能 仅调用 1 次。
    • 引数 N 是星星的数量 N 。从
    • 引数 M 是扭曲设备的数量 M 。从
    • 引数 U, V 是长度 它是一个 N 数组,0 \leqq i \leqq M - 1 , 写出第U[i], V[i] 是一个扭曲设备 i 双向连接的星数 可以在 U_i, V_i 。从

thief.cpp 内调用以下函数。

  • int query(std::vector<int> x)
    • 使用此功能提出问题。 它是一个
    • 引数 x 是长度 它是一个 M 数组。 当0 \leqq i \leqq M - 1 , 写出第x[i] 是 存在 0 时扭曲装置 关于 i ,星 要单向连接到 U_i 卡拉星 V_i , 表示单向连接到1 时扭曲装置 关于 i ,星 要单向连接到 V_i 卡拉星 U_i 。
    • 返回值为 0 或 1 。返回值为 0 当使用一些扭曲设备来 事实上,您无法移动到 A 卡拉星 B 你无法搬到的地方1 当明星 表示您可以移至 A 卡拉星 B 。
    • 引数 x 的长度是 必须是 M 。如果不满足这一点,不正解 [1] 已确定。
    • 引数 x 的每个元素是 调用次数不得超过0 或 1 。如果不满足这一点,不正解 [2] 已确定。
    • 関数 query 除以 300 次。 如果调用次数超过300 次,不正解 [3] 已确定。
  • void answer(int A, int B)
    • 使用此功能可以回答隐藏钥匙的星星的编号和隐藏宝箱的星星的编号。
    • 引数 A 是0 以上 N - 1 的整数。带隐藏钥匙的星号 A 。
    • 引数 A 是0 以上 N - 1 。如果不满足这一点,不正解 [4] 已确定。
    • 引数 B 是0 以上 N - 1 的整数。宝箱隐藏的星星编号 B 。
    • 引数 B 是0 以上 N - 1 。如果不满足这一点,不正解 [5] 已确定。
    • 如果您回答错误的星星号码,不正解 [6] 已确定。
    • 関数 answer 只是 1 次。功能 如果调用次数超过 answer 除以 2 次,不正解 [7] 被确定。功能 solve 执行结束时的函数 如果没有被调用 answer 是 存在 1 次,不正解 [8] 已确定。

重要说明

  • 您可以自由地实现其他函数并声明全局变量以供内部使用。
  • 您提交的程序不得以任何方式与标准输入、标准输出或其他文件交互。但是,允许将调试信息等输出到标准错误输出。

如何编译执行

用于测试创建的程序的示例评分程序是 它包含在可以从竞赛网站下载的存档中。 该存档还包含必须提交的示例文件。

评分程序的示例是 1 由两个文件组成。 该文件是 grader.cpp 。 为了测试你的程序, 这些文件 将 grader.cpp, thief.cpp, thief.h 放在同一目录中并运行以下命令。

g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp

存档中还包含 您可以改为运行文件 compile.sh 。在这种情况下,请运行以下命令。

./compile.sh

如果编译成功, 将生成一个名为grader 的可执行文件。

请注意,实际评分程序与示例评分程序不同。 示例评分程序作为单个进程运行。 该程序从标准输入读取输入并将结果输出到标准输出。

输入示例评分程序

示例评分程序按以下格式从标准输入读取输入。

N M A B
U_0 V_0
U_1 V_1
\vdots
U_{M-1} V_{M-1}

评分程序的示例输出

示例评分程序将以下信息输出到标准输出(引号实际上并未输出)。

  • 如果正确,则函数 呼叫 query 的次数是 其输出类似于 Accepted: 25 。
  • 如果答案不正确,则错误答案的类型为 Wrong Answer [4] 。

如果要执行的程序满足多个不正确的条件, 显示的错误答案类型有 1 只有一个。如果满足错误答案条件,示例评分程序可能会中途终止执行。

评分注意事项

对于某些测试用例,实际评分程序是自适应的。 这是因为评分程序从一开始就没有固定的答案,并且 query 这意味着评分程序响应函数调用而做出响应。 但是,如果与所有响应一致的答案至少是 1 保证存在。

制約

所有输入数据满足以下条件。

  • 2 \leqq N \leqq 10\,000.
  • 1 \leqq M \leqq 15\,000.
  • 0 \leqq A \leqq N - 1.
  • 0 \leqq B \leqq N - 1.
  • A \neq B.
  • 0 \leqq U_i < V_i \leqq N - 1 (0 \leqq i \leqq M - 1).
  • (U_i, V_i) \neq (U_j, V_j) (0 \leqq i < j \leqq M - 1).
  • 哪个 2 你可以使用一些扭曲装置在两颗恒星之间旅行。

小課題

  1. (7 点) M = N - 1,U_i = i,V_i = i + 1 (0 \leqq i \leqq M - 1).
  2. (13 点) M = N - 1,U_i = 0,V_i = i + 1 (0 \leqq i \leqq M - 1).
  3. (2 点) M = N - 1,N \leqq 8.
  4. (8 点) M = N - 1,N \leqq 50.
  5. (5 点) M = N - 1,N \leqq 150.
  6. (5 点) M = N - 1,N \leqq 250.
  7. (40 点) M = N - 1.对于此子任务,将根据以下方式确定分数: 关于
    • 小課題 7 对应的测试用例,1 如果有任何错误答案,则该子任务的分数将为 0 成为重点。
    • 否则,该函数 query 的最大调用次数为 T 。此时,子任务的分数确定如下。
      • 120 < T 时, 表示第20 点.
      • 70 < T \leqq 120 时, 表示第30 点.
      • T \leqq 70 时, 表示第40 点.
  8. (20 点)没有额外的限制。对于此子任务,将根据以下方式确定分数:
    • 小課題 8 对应的测试用例,1 如果有任何错误答案,则该子任务的分数将为 0 成为重点。
    • 否则,该函数 query 的最大调用次数为 T 。此时,子任务的分数确定如下。
      • 120 < T 时, 表示第10 点.
      • 70 < T \leqq 120 时, 表示第15 点.
      • T \leqq 70 时, 表示第20 点.

小課題 1,2,3,4,5,6 的分数是一个函数 无论对 query 的调用次数(300 次或更少),但是 如果数量超过70 ,竞赛网站可能会表明输出部分正确。


交互示例

入力例 1

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

1 第 query 函数调用对应的选择如下。

  • 扭曲装置 沿一个方向连接至 0 ,星 要单向连接到 0 卡拉星 1 。
  • 扭曲装置 沿一个方向连接至 1 ,星 要单向连接到 3 卡拉星 0 。
  • 扭曲装置 沿一个方向连接至 2 ,星 要单向连接到 1 卡拉星 2 。
  • 扭曲装置 沿一个方向连接至 3 ,星 要单向连接到 1 卡拉星 4 。

在此选择下,明星 0 卡拉星 4 扭曲装置 您可以按此顺序使用 0, 3 进行移动,因此返回值为 1 变为。 由于使用某些扭曲设备无法前往

2 第 query 函数调用对应的选择如下。

  • 扭曲装置 沿一个方向连接至 0 ,星 要单向连接到 1 卡拉星 0 。
  • 扭曲装置 沿一个方向连接至 1 ,星 要单向连接到 3 卡拉星 0 。
  • 扭曲装置 沿一个方向连接至 2 ,星 要单向连接到 2 卡拉星 1 。
  • 扭曲装置 沿一个方向连接至 3 ,星 要单向连接到 1 卡拉星 4 。

在此选择下,明星 0 卡拉星 4 ,因此返回值为 由于可以使用多个扭曲设备前往 0 变为。 由于使用某些扭曲设备无法前往

3 第 query 函数调用对应的选择如下。

  • 扭曲装置 沿一个方向连接至 0 ,星 要单向连接到 0 卡拉星 1 。
  • 扭曲装置 沿一个方向连接至 1 ,星 要单向连接到 0 卡拉星 3 。
  • 扭曲装置 沿一个方向连接至 2 ,星 要单向连接到 2 卡拉星 1 。
  • 扭曲装置 沿一个方向连接至 3 ,星 要单向连接到 1 卡拉星 4 。

在此选择下,明星 0 卡拉星 4 ,因此返回值为 1 变为。 由于使用某些扭曲设备无法前往

4 第 query 在函数调用对应的选择下,星号 0 卡拉星 4 ,因此返回值为 由于可以使用多个扭曲设备前往 0 变为。 由于使用某些扭曲设备无法前往

answer 函数调用中的星号 A 是一颗星星 0 和一颗星星 这表明答案是 B 是一颗星星 4 。

此输入示例是一个小作业。 满足 3,4,5,6,7,8 满足约束。在可以从竞赛网站下载的存档中包含的文件中,sample-01-in.txt 是一个输入示例 对应于 1 。

必须提交的示例文件中的函数调用与这些函数调用相同,这些文件包含在可从竞赛网站下载的存档中。 编号至