「EZEC-14」终点

Luogu

IDLGP9462

Time1000ms

Memory512MB

DifficultyP6

二分洛谷原创交互题Special JudgeO2优化广度优先搜索 BFS深度优先搜索 DFS洛谷月赛

**这是一道交互题。** dXqwq 有一棵 $n$ 个点的无根树，结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。您可以选择两个整数 $1\leq u,v\leq n$，并输出 `? u v` 进行询问。对于每次询问，如果 $u,v$ 的路径中点在一个结点上，交互库返回该点的编号，否则返回 ``0``。请通过不超过 $147154$ 次询问，得到这棵树的结构。保证树的形态是提前确定的，即**交互库不自适应。** ### 交互方式输入测试点所在子任务编号 $id$ 和树的大小 $n$ 以开始交互。交互过程中，您可以进行题目描述中的询问。对于每次询问，如果你提供的 $u,v$ 不合法或者超出询问次数上限，交互库会返回 ``-1``，否则交互库将会返回一个非负整数，含义见「题目描述」。当你读取到 ``-1`` 后应立刻退出程序，在此之后交互库的行为未定义。在您确定答案后，请先输出 `!`，然后接下来 $n-1$ 行依次输出两个整数 ``u[i] v[i]`` 代表树的每条边，最后退出程序。你可以以任意顺序输出这些边。在您输出一行后，请清空缓冲区： - 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 - 在 Pascal 中，使用 `flush(output)`。 - 在 Python 中，使用 `stdout.flush()`。 - 其它语言请自行查阅文档。 ## Input 见「交互方式」。 ## Output 见「交互方式」。 [samples] ## Background ~~出题人怎么还没鸟加这首歌啊。~~ 于 2023.8.5 拿下。 ## Note **本题采用捆绑测试。** - Subtask 1（10 pts）：$n \leq 10$，树满足性质 A。 - Subtask 2（10 pts）：保证存在一个点度数为 $n-1$。 - Subtask 3（10 pts）：保证所有点度数 $\leq 2$。 - Subtask 4（10 pts）：$n \leq 500$，树满足性质 A。 - Subtask 5（20 pts）：$n \leq 500$。 - Subtask 6（20 pts）：树满足性质 A。 - Subtask 7（20 pts）：无特殊限制。性质 A：对于 $i=2,3,\cdots,n$ 存在整数 $1\leq j<i$ 满足有一条边连接 $i,j$。对于 $100\%$ 的数据，$2 \leq n \leq 10^4$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/3u2zy1q5.png)

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「EZEC-14」终点",
    "description": {
      "content": "**这是一道交互题。** dXqwq 有一棵 $n$ 个点的无根树，结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。 您可以选择两个整数 $1\\leq u,v\\leq n$，并输出 `? u v` 进行询问。 对于每次询问，如果 $u,v$ 的路径中点在一个结点上，交互库返回该点的编号，否则返回 ``0``。 请通过不超过 $147154$ 次询问，得到这棵树的结构",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9462"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**这是一道交互题。**\n\ndXqwq 有一棵 $n$ 个点的无根树，结点从 $1$ 到 $n$ 编号。您需要通过若干次询问得到这棵树的结构。\n\n您可以选择两个整数 $1\\leq u,v\\leq n$，并输出 `? u v` 进行询问。\n\n对于每次询问，如果 $u,v$ 的路径中点在一个结点上，交互库返回该点的编号，否则返回 ``0``。\n\n请通过不超过 $147154$ 次询问，得到这棵树的结构...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments