← 返回题目列表

AtCoder · joig2026final_l

L. 电压2

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

配点 : 100 点

分发文件

問題文

你听说过 Just Odd Inventions 吗?这家公司的业务“只是一项奇怪的发明”。 发明)。这里,我们将其简称为JOI。

JOI 的实验室里有一个复杂的电路。 该电路是 N 节点和 M 它由一个又长又细的电阻组成,节点是 高达 0 从 N - 1 的电阻为 它们的编号最大为 0 从 M - 1 。 每个节点都可以设置为“高电压”或“低电压”状态。 电阻 i (0 \leqq i \leqq M - 1) 是一个节点 与 A_i 不同的节点 它连接到 B_i ,并且节点 A_i 是“高电压”,节点 仅当 B_i 处于“低电压”状态时电流才会流动。 在其他情况下,没有电流流动。 另外,任何 2 连接两个节点的电阻最多为 1 仅存在书籍。

作为 JOI 的研究员,您将使用该电路进行实验。 该电路中的电阻又长又细,无法目视确认电阻连接了哪些节点。 然而,有一条线索表明,在设置每个节点的电压时,电路的温度会根据电流流过的电阻的数量而增加。 因此,设置电压后,您决定通过触摸电路来读取温度。 您无法准确读取电路的温度,但可以设置电压 您可以执行 2 次并比较哪个设置导致更高的温度。 换句话说,电压设置 通过指定 2 次,您可以获得以下任意信息。

  • 1 在第二电压设置中电流流过的电阻的数量更大。 对于
  • 2 电压设置,电流流过的电阻数量相同。
  • 2 在第二电压设置中电流流过的电阻的数量更大。 对于

您的目标是反复比较这些温度,以确定从哪个节点到哪个节点的所有电阻。 预先确定节点数 N,电阻数 给出了 M 。 此外,电阻连接不同的节点,并且任何 2 连接两个节点的电阻最多为 1 我也知道这是一本书。 在这种条件下,根据温度比较获得的信息,我们可以确定电路中通过电阻连接的一对节点。 识别 (a, b) 的所有集合。 然而,根据电路的结构,无论进行多少次比较,都可能无法唯一地识别电阻的连接。 在这种情况下,需要报告无法识别。

为防止电阻恶化,应比较实际温度。 您最多只能执行 30\,000 次。

JOI 使用这个奇怪的电路做出了什么发明是公司内部的最高机密,除了总裁之外没有人知道。

给定电路节点的数量和电阻, 编写一个程序,通过比较小于或等于30\,000 的温度来确定电路的电阻,或报告无法确定电路的电阻。

实施细节

你的答题程序是voltage.h 分成 #include 必须使用预处理器指令来读取它,并且必须实现以下功能。

  • bool solve(int N, int M)
    • 该函数是 在 1 处决中 仅调用 1 次。
    • 引数 N 是电路中的节点数 N 。
    • 引数 M 是电路中的电阻数 M 。
    • 当无论比较多少次温度都无法唯一识别电阻的连接时,使用此功能。 false ,否则 必须返回 true 。
    • 虽然无法识别电阻的连接 如果返回 true ,不正解[1] 已确定。
    • 虽然可以通过比较温度来识别电路 false ,不正解[2] 已确定。

您的程序可以调用以下函数。

  • int query(std::vector<int> x, std::vector<int> y)
    • 您可以使用此功能来设置电压 2 次并比较温度。
    • 引数 x 为 1 使用参数第二次设置电压 y 为 2 第二次指定电压设置。 必须是
    • 引数 x 和 y 为 0 和 1 组成长度为 N 数组。
    • x[k] (0 \leqq k \leqq N - 1) 是 1 如果 第 1 在设置电压时,节点 k 是“高电压”, x[k] 是 0 然后节点 k 表示设置为“低电压”。
    • y[k] (0 \leqq k \leqq N - 1) 是 1 如果 第 2 在设置电压时,节点 k 是“高电压”, y[k] 是 0 然后节点 k 表示设置为“低电压”。
    • 该函数的返回值为 1 设置电压和 2 这是在第二个电压设置下比较温度的结果。 它是值-1,0,1之一。
      • 返回值为 当-1时,1 第二次更好,2 这表明第二次电流流过的电阻数量大于电压设置。
      • 返回值为 当0时,1 次和2 表示在第二电压设置下电流流过的电阻数量相同。
      • 返回值为 当1时,2 第二次更好,1 这表明第二次电流流过的电阻数量大于电压设置。
    • 引数 x 的长度是 如果不是 N ,不正解[3] 已确定。
    • 引数 x 于 0 但是 如果包含的值不是 1 ,不正解[4] 已确定。
    • 引数 y 的长度是 如果不是 N ,不正解[5] 已确定。
    • 引数 y 于 0 但是 如果包含的值不是 1 ,不正解[6] 已确定。
    • 此功能 调用次数不得超过 30\,000 次。 如果调用次数超过30\,000 次,不正解[7] 已确定。
  • void answer(int a, int b)
    • 使用此功能可以回答指定的电阻。
    • 引数 a, b 是一个节点 a 到节点 它表示有一个电阻连接到 b 。 必须是
    • 0 \leqq a \leqq N - 1 和 0 \leqq b \leqq N - 1 。如果不满足这一点 不正解[8] 已确定。
    • 相同 (a, b) 对作为参数 调用次数不得超过 2 次。如果不满足这一点 当返回 不正解[9] 已确定。
    • 此功能 调用次数不得超过 M 次。 如果调用次数超过M 次,不正解[10] 已确定。
    • 関数 solve 是 true 时,该函数 answer 只是 一定已被调用 M 次。 如果这还不满足, 所有元组作为参数传递给不正解[11] 已确定。
    • 関数 solve 是 true 时,该函数 answer 对于 (a, b) ,节点 实际上必须有一个电阻连接到 a 到节点 它表示有一个电阻连接到 b 。 如果这还不满足,不正解[12] 已确定。

重要说明

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

如何编译执行

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

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

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

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

./compile.sh

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

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

输入示例评分程序

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

N M
A_0 B_0
\vdots
A_{M-1} B_{M-1}

评分程序的示例输出

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

  • 如果出现错误答案 [3] 至 [12] 中的任何一个,则错误答案类型为“ 输出Wrong Answer [5]“。
  • 否则,该函数 调用 query 的次数和函数 solve 的返回值为“ 输出Accepted: 30 true“。 与实际评分程序不同,示例评分程序要么不正确 [1]、[2],要么是一个函数 请注意,我们不检查 solve 的返回值是否正确。

当满足 [3] 到 [12] 中的任何错误答案条件时,示例评分程序结束执行。 如果要执行的程序满足错误答案[3]至[12]中的多个条件,则显示的错误答案类型将是其中之一。 1 只有一个。

评分注意事项

实际评分程序不是自适应的,而是从交互开始就有固定的答案。


制約

  • 2 \leqq N \leqq 500.
  • 1 \leqq M \leqq 1\,000.
  • 0 \leqq A_i \leqq N - 1 (0 \leqq i \leqq M - 1).
  • 0 \leqq B_i \leqq N - 1 (0 \leqq i \leqq M - 1).
  • A_i \neq B_i (0 \leqq i \leqq M - 1).
  • (A_i, B_i) \neq (A_j, B_j) 和 (A_i, B_i) \neq (B_j, A_j) (0 \leqq i < j \leqq M - 1).
  • N, M, A_i, B_i 是一个整数 (0 \leqq i \leqq M - 1).

小課題

  1. (4 点) N = 2.
  2. (16 点) N \leqq 100,M = N - 1,B_i = A_{i+1} (0 \leqq i \leqq N - 3),N 值 A_0, A_1, \ldots ,A_{N-2}, B_{N-2} 都是不同的。
  3. (21 点) M = N - 1,B_i = A_{i+1} (0 \leqq i \leqq N - 3),N 值 A_0, A_1, \ldots ,A_{N-2}, B_{N-2} 都是不同的。
  4. (24 点) N \leqq 100,A_i \neq A_j (0 \leqq i < j \leqq M - 1).
  5. (14 点) A_i \neq A_j (0 \leqq i < j \leqq M - 1).
  6. (11 点) N \leqq 100.
  7. (10 点)没有额外的限制。

交互示例

下面是示例评分程序读取的输入示例以及相应函数调用的示例。

入力例 1

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

1 第 在对 \texttt{query} 的通话中 2 电压设置和电流流过的电阻如下。

  • 1 第二次是一个节点 0, 1 到“低电压”,节点 将 2, 3, 4 设置为“高电压”。此时,电阻 电流流过 1, 5 。
  • 2 第二次是一个节点 3, 4 到“低电压”,节点 将 0, 1, 2 设置为“高电压”。此时,电阻 电流流过 2 。

1 返回值为 -1 。

此输入示例是一个小作业。 6, 7 满足约束。

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