#1899. 前往何方
前往何方
前往何方
题目描述
第三试前往何方(wheretoreach) IOI2025 中国国家集训队集中培训 前往何方(wheretoreach) .这.是.一.道.交.互.题。 【题目描述】 有一棵n 个点的树,你不知道其形态。你有一个初始为空的点集S。你可以进行以 下两种操作:
- 向S 中加入一个结点。
- 从S 中删除一个结点。 每次操作结束后,交互库将会返回树对S 的导出子图(即仅保留S 中的点和两端 都在S 中的边得到的图)的最大连通块大小。 你需要使用尽可能少的操作还原树的结构。 【实现细节】 请确保你的程序开头有#include "wheretoreach.h"。 你不需要也不应该实现主函数。你需要实现以下函数: void solve (int n); 1 • 其中n 表示树的结点个数,结点从1 至n 编号。 你可以调用下列由交互库提供的函数: int add (int x); 1 int remove (int x); 2 void report (int x,int y); 3 • add(x) 用于向S 中加入一个结点x,若x 本身就在S 中则什么也不做。 – 你需要保证1 ≤x ≤n。 – 该函数返回值为操作后S 的导出子图最大连通块大小。 • remove(x) 用于从S 中删除一个结点x,若x 本身就不在S 中则什么也不做。 – 你需要保证1 ≤x ≤n。 – 该函数返回值为操作后S 的导出子图最大连通块大小; • report(x,y) 表示你找到了树的一条边(x, y)。 – 你需要恰好调用该函数n −1 次以提交树的所有边。边的顺序和方向任意。 你调用add 与remove 的总次数不得超过2 × 106。 保证在满足题目条件和数据范围的情况下,最终测试时交互库的运行时间不会超过 2000 ms,运行空间不会超过128 MiB。 .交.互.库.不.是.自.适.应.的,.即.树.形.态.固.定,.不.会.随.着.交.互.过.程.改.变。 第6 页 共8 页 第三试前往何方(wheretoreach) IOI2025 中国国家集训队集中培训 【测试程序方式】 .试.题.目.录.下.的implementer.cpp .是.我.们.提.供.的.交.互.库.参.考.实.现。.最.终.测.试.的.交.互 .库.与.样.例.交.互.库.有.一.定.不.同,.故.你.的.实.现.不.应.该.依.赖.样.例.交.互.库.实.现。 你需要在本题目录下使用如下命令编译得到可执行程序: g++ implementer.cpp sample.cpp ‐o sample ‐O2 ‐‐std=c++14 ‐lm 对于编译得到的可执行程序: • 可执行文件将从标准输入读入以下格式的数据: – 第一行一个整数n 表示树的点数。你需要保证1 ≤n ≤104。 – 接下来n −1 行,每行两个整数x, y 描述树上的一条边。边的顺序和方向是 任意的。 • 读入完成之后,交互库将调用恰好一次函数solve。 • 当你的实现不符合【实现细节】中的要求时,交互库只会在标准输出流输出一行 一个整数‐1。具体地,以下情况发生时交互库会输出‐1: – 对add 和remove 的函数调用中传入了不满足1 ≤x ≤n 的x; – 调用add 和remove 的次数和超过了2 × 106; – solve 函数结束时report 函数的调用次数不为n −1。 • 否则,交互库会在标准输出流按照以下格式输出: – 第一行两个整数Q, c,Q 表示你调用add 和remove 的总次数,c = 1 表示 你的答案正确,c = 0 表示不正确。 – 接下来若干行,为你调用add,remove 和report 的记录,其格式可以参 考样例1。 【样例1 输入】 3 1 1 2 2 2 3 3 【样例1 输出】 4 1 1 add(2); 2 add(3); 3 add(1); 4 remove(2); 5 第7 页 共8 页 第三试前往何方(wheretoreach) IOI2025 中国国家集训队集中培训 report(3,2); 6 report(1,2); 7 【样例1 解释】 该样例输出为下发的样例程序在该组样例下的输出。 【子任务】 对于所有测试数据,1 ≤n ≤104。 Subtask 1 (10%):n = 500。 Subtask 2 (20%):n = 2500。 Subtask 3 (70%):n = 104。 【评分方式】 .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制都会导致相应测试点得0 分。选手只能在程序中 访问自己定义的和交互库给出的变量或数据,及其相应的内存空间。尝试访问其他位置 空间将可能导致编译错误或运行错误。 对于Subtask 1,2 中的测试点,只要你的交互符合【实现细节】中的规则,且给出 了正确答案,则可以获得满分。 对于Subtask 3 中的测试点,在你的交互符合【实现细节】中的规则,且给出了正 确答案的基础上,设你调用add 和remove 的总次数为Q,你的得分为f(Q),其中 (0.0 × 106 ≤Q ≤0.6 × 106) 70 (0.6 × 106 < Q ≤0.7 × 106) 70 −Q−0.6×106 5000 (0.7 × 106 < Q ≤1.0 × 106) 50 −Q−0.7×106 f(Q) = 15000 (1.0 × 106 < Q ≤1.5 × 106) 30 −Q−1.0×106 25000 (1.5 × 106 < Q ≤2.0 × 106) 10 −Q−1.5×106 50000 是一个连续的分段线性函数。你可以理解为:你的前0.6 × 106 次调用是免费的;此 后的0.1 × 106 次调用中每5000 次扣1 分;随后的0.3 × 106 次调用中每15000 次扣1 分;随后的0.5 × 106 次调用中每25000 次扣1 分;随后的0.5 × 106 次调用中每50000 次扣1 分。 你在每个子任务上获得的分数为在其中所有测试点上分数的最小值。 .选.手.不.应.通.过.非.法.方.式.获.取.交.互.库.的.内.部.信.息,.如.试.图.与.标.准.输.入、.输.出.流.进.行.交 .互。.此.类.行.为.将.被.视.为.作.弊。 第8 页 共8 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
1 2
2 3
4 1
add(2);
add(3);
add(1);
remove(2);
report(3,2);
report(1,2);