云小安的系统

\\n\\n> 此题仅允许使用 C++ 语言提交。\\n\\n## 题目背景\\n\\n跨年夜的灯会布线是一棵树。云小安设计的系统里藏着两盏故障灯 $s\\\\neq t$，它们会在 $0$ 点前熄灭。你看不到它们的编号，但你有一台“回声指引器”。\\n\\n你对任意节点 $x$ 发起一次探测，指引器会分别给出“从 $x$ 出发，朝着 $s$ 走的第一步”和“从 $x$ 出发，朝着 $t$ 走的第一步”。但为了防止你区分哪一步对应哪盏灯，指引器会把这两步**排序后**返回。\\n\\n你需要在有限探测次数内找出 $s,t$。\\n\\n\\n## 题目描述\\n\\n本题为**函数交互题**。\\n\\n存在一棵无向树 $T$，节点编号为 $1\\\\dots n$，$T$ 连通且无环。\\n\\n存在两个互不相同的隐藏节点 $s\\\\neq t$。\\n\\n对任意节点 $x$ 与目标 $y\\\\in\\\\{s,t\\\\}$，定义：\\n- 若 $x=y$，则 $\\\\mathrm{step}(x,y)=x$；\\n- 否则 $\\\\mathrm{step}(x,y)$ 为 $x$ 的一个邻点，且位于从 $x$ 到 $y$ 的唯一路径上（即从 $x$ 朝 $y$ 走的第一步）。\\n \\n\\n一次询问 `query(x)` 会返回两个整数 $a\\\\le b$，满足：\\n\\n$$\\n\\\\{a,b\\\\}=\\\\{\\\\mathrm{step}(x,s),\\\\ \\\\mathrm{step}(x,t)\\\\}.\\n$$\\n\\n注意返回的是**排序后的结果**，因此你无法知道哪一个对应 $s$、哪一个对应 $t$。\\n\\n你的任务是在询问次数限制内，输出这两个隐藏节点 $s,t$（顺序任意）。\\n\\n\\n## 交互库与接口说明\\n\\n你可以调用 `light.h` 进行交互，交互命令有以下四种。\\n\\n### `int getn()`\\n\\n返回整数 $n$，满足：\\n- $2 \\\\le n \\\\le 2\\\\cdot 10^5$。\\n\\n你应当在程序一开始调用此函数，并且**仅调用一次**。\\n\\n\\n### `void geted(int i, int &u, int &v)`\\n\\n获取树的第 $i$ 条边（$1\\\\le i\\\\le n-1$），返回该边两端点 $u,v$。\\n- 保证 $1\\\\le u,v\\\\le n$ 且 $u\\\\neq v$。\\n\\n### `void query(int x, int &a, int &b)`\\n\\n询问节点 $x$（要求 $1\\\\le x\\\\le n$），返回两个整数 $a,b$（按从小到大排序，即保证 $a\\\\le b$），满足：\\n\\n$$\\n\\\\{a,b\\\\}=\\\\{\\\\mathrm{step}(x,s),\\\\ \\\\mathrm{step}(x,t)\\\\}.\\n$$\\n\\n你最多可以调用 `query` **$Q$** 次，其中：\\n\\n$$\\nQ = 3\\\\cdot \\\\left\\\\lceil \\\\log_2 n \\\\right\\\\rceil + 20.\\n$$\\n\\n超过次数将被判定为错误（RE/WA）。\\n\\n\\n### `void submit(int s, int t)`\\n\\n当你确定故障灯位置后，调用此函数提交答案。\\n\\n要求：\\n- $1\\\\le s,t\\\\le n$；\\n- $s\\\\neq t$。\\n\\n允许输出顺序任意：`submit(s,t)` 与 `submit(t,s)` 等价。\\n\\n提交后你不应当再进行任何交互操作。\\n\\n\\n \\n\\n## 数据范围\\n\\n对于 $15\\\\%$ 的数据，满足 $n\\\\le 2000$。\\n \\n对于另 $25\\\\%$ 的数据，满足 $n\\\\le 5\\\\times 10^4$。\\n \\n对于 $100\\\\%$ 的数据，满足 $n\\\\le 2\\\\times 10^5$。\\n\\n对所有测试点：询问次数上限均为 $Q=3\\\\lceil\\\\log_2 n\\\\rceil+20$。\\n\\n交互库请从 [附件](https://dtoj.team/contest/6946e4249c350a2c531f5f73/file/light.h) 下载，不保证其实现一定与评测时采用的交互库相同。\

统计

递交统计

云小安的系统

信息

还没有账户？

登录