← 返回题目列表

AtCoder · pakencamp_2025_day2_h

H. 沉没群岛

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

配点 : 100 点

問題文

这个问题是一个交互问题。

To Pa Kenyo N 岛屿漂浮着, 它的编号为1,2,\dots,N 。

还连接岛屿 有 N-1 桥梁,i 第二座桥是一座岛 U_i 和岛屿 V_i 是平局。在这里,您可以通过几次桥梁从任何一个岛屿到达另一个岛屿。

K主管试图将所有这些岛屿置于他的控制之下,但他不知道桥梁的结构。因此,我决定通过向了解桥梁结构的黑豹变色龙帕塔罗重复以下问题来识别桥梁的结构。

  1. K酋长管理着这座岛屿。 1 個以上 N 选择一个或更少并告诉帕塔罗。
  2. 帕塔罗将满足以下条件。 N 当沉没一些岛屿时,告诉 K 总监可以不沉没的最大岛屿数量。
    • 所有未沉没的岛屿均由K主任选择。
    • 你可以通过多次过桥到达任何未沉没的岛屿。
    • 对于每个未沉没的岛屿,最多有 2 一。

请注意,这是帕塔罗的思想实验,所以他实际上不会沉没岛屿。

帕塔罗也没有空闲时间,所以 您最多只能回答此问题L 次。

考虑到帕塔罗上漂浮的岛屿数量以及可以向帕塔罗提出的问题数量,实施K主任的策略来找出哪些岛屿是通过桥梁连接的。

制約

  • N = 256
  • 1 \leq U_i,V_i\leq N (1\leq i\leq N-1)
  • 多次过桥就可以到达任何岛屿。

小課題

  1. (5 点) L=33000
  2. (25 点) L=10000
  3. (20 点) L=6400
  4. (50 点) L=4600

入出力

首先,N,L 由标准输入给出。

N L

接下来,你去帕塔罗。 问以下问题 L 次。您选择的岛屿 s_1,s_2,\dots,s_n ,按以下格式输出。

? n s_1 s_2 \dots s_n

当您提出问题时,您将收到帕塔罗的回复。 X 由标准输入给出。

X

在这里,X 是一个整数,

  • X\ne -1 当问题的答案是 X 。
  • X=-1 ,提出的问题数为 L 表示问题数量超出或问题不符合格式。
    • 此时,程序已经被判定为错误。立即终止程序。

如果您可以识别桥的结构,请按以下格式输出。这不计算在提出的问题数量中。

! u_1 v_1 u_2 v_2 \dots u_{N-1} v_{N-1}

在这里,每个 i 关于岛屿 必须有一座桥连接 u_i 和岛屿 v_i 。另外,请勿多次应答同一网桥。此输出后立即退出程序。

如果输出不符合上述任何格式,-1 由输入给出。

-1

此时,程序已经被确定为错误的。立即终止程序。

注意点

  • 每次打印输出时,在末尾插入换行符并刷新标准输出。如果不这样做,判断结果将是 可能会发生 TLE 。
  • 当你输出答案时,或者 当您从标准输入接收到 -1 时,立即终止程序。如果不这样做,则确定结果是不确定的。
  • 请注意,额外的换行符被视为格式错误的输出。
  • 本题的判断系统不具有自适应性。 换句话说,U 和 V 在与评委互动之前确定,并且不得随时更改。 显示

入出力例

N=5,U=(1,2,2,2),V=(2,3,4,5),L=10 时的对话示例。

入力 出力 説明
5 10 首先是一个整数 向 Pataro 发送问题 N,L 由标准输入给出。
? 2 1 2 s=(1,2) 。
2 输出满足约束,因此该岛 因为除了 1,2 之外,下沉是最佳的 2 被给予。
? 4 1 3 4 5 s=(1,3,4,5) 。
1 输出满足约束,因此该岛 因为除了 1 之外,下沉是最佳的 1 被给予。
? 4 2 3 4 5 s=(2,3,4,5) 。
3 输出满足约束,因此该岛 因为除了 2,3,4 之外,下沉是最佳的 3 被给予。
! 1 2 3 2 5 2 2 4 我们报告说桥梁的结构已经确定。正确答案是通过在此输出后立即终止程序来确定的。

请注意,这是一个对话的示例。特别是,根据目前给出的问题和答案,并不总是能够可靠地识别桥梁的结构。

请注意,此案例不满足约束条件,因此不包含在实际评分测试案例中。