UOJ Logo Universal Online Judge

UOJ

#693. 【UR #23】地铁规划

附件下载 统计

这是一道交互题。

新首都跳蚤利亚需要建立地铁线路!hehe 蚤负责了这个项目。

跳蚤利亚有 $n$ 个地铁站,还有 $m$ 条线路计划设立,第 $i$ 条铁轨将在 $u_i$ 和 $v_i$ 之间建立一条双向线路($u_i\neq v_i$)。可能有两条线路连接的地铁站相同。

由于跳蚤利亚是面向未来的节能环保城市,hehe 蚤希望地铁的建设也要避免浪费。hehe 蚤仔细地审查工程建设方案,并定义了什么叫做“绿色区间”:对于任何满足 $1 \le l \le r \le m$ 的整数 $l, r$,我们称 $[l, r]$ 是一个区间;如果在只修建所有 $u_i, v_i \in [l, r]$ 的线路的情况下,地铁网络不包含环,那么我们称这个区间是绿色的。

hehe 蚤突然好奇:有多少个区间 $[l, r]$ 是绿色的呢?但这样的好奇持续了 $10^{-9}$ 秒后, hehe 蚤就想到了做法。如果一个区间是绿色的,那它的子区间也是绿色的。于是可以用双指针,对于所有的区间左端点 $l\in[1,m]$,计算出使得 $[l, r]$ 是绿色的最大的右端点值 $r$ 即可。而维护是否有环这一信息,只需使用跳蚤国最新自研数据结构 hehe 树。

作为跳蚤国顶级科学家之一,hehe 蚤刚在大量系统中植入了 hehe 树,所以这问题已经变得没意思了。为了挑战自我,hehe 蚤拿出了一台植入 hehe 树失败的机器,仅包含部分 hehe 树功能。具体来说,这台机器支持:

  1. 给定 $id$,在图中建立双向线路 $u_{id}, v_{id}$,注意,如果假如建立后图中产生了环,机器会报错。

  2. 拆除图中加入时间最晚的一条双向线路。

  3. 给定 $id$,询问 $u_{id}, v_{id}$ 两点间是否可以通过已经建立的双向线路连通。

拿出了这台机器后,hehe 蚤又得出了一个基于分治的强大的做法,并给出了答案。hehe 蚤大呼简单。

但 hehe 蚤又想了想,觉得自己应该在跳蚤国内弘扬这股 “麻烦自己,麻烦别人” 的挑战精神。于是 hehe 蚤把这台机器交给了你。他会从小到大依次对每个左端点 $l\in [1,m]$,向你询问,所有以 $l$ 为左端点的绿色区间 $[l, r]$ 中最大的右端点值 $r$。因为 hehe 蚤觉得这个问题太简单,所以在你计算答案 $r$ 时,你不可以让机器加入编号大于 $r$ 的线路。

一句话题意:有一个长度为 $m$ 的边序列,你需要使用交互库提供的可撤销并查集接口,在线地对于每个 $l$ 求出最大的 $r$,使得区间 $[l,r]$ 内的边不形成环。

任务

本题仅支持 C++。

你必须引用 subway.h 头文件。

你需要实现下面的过程:

void init(int n, int m, int lim);

这个过程将在所有 solve 调用前,恰好被调用一次。

其中 $n$ 表示地铁站数量,$m$ 表示线路数量,$\textit{lim}$ 表示你可以使用 merge 次数的上限。

int solve(int l);

这个过程将被调用恰好 $m$ 次,且第 $i$ 次调用的 l 一定是 $i$。你需要返回 $r_l$ 表示最大的 $r$ 满足区间 $[l,r]$ 中的边不成环。

你可以在 solve 的过程中调用以下过程和交互库交互:

void merge(int x);

这个函数的作用是建立双向线路 $u_x,v_x$。

这个函数只能在 solve 过程中被调用,并且必须满足 $x\in [l, r_l]$,其中 $l$ 是当前 solve 过程的参数,以及加入这条边不会使 hehe 树维护的图成环,否则你的交互过程会被判定为失败。

你调用这个函数的次数不能超过 $\textit{lim}$ 次,并且如果你调用这个函数的次数超过了 $2\times 10^7$,你的交互过程将被判定为不合法。

void undo();

这个函数将撤销最后一次没有被撤销的 merge 操作,如果没有可以被撤销的 merge 操作,你的交互过程会被判定为失败。

bool check(int x);

如果 $u_x$ 和 $v_x$ 联通,函数将返回 false,否则返回 true

换言之,返回值表示加入第 $x$ 条线路是否不会成环。

不同 solve 轮次间 hehe 蚤维护的图将被保留,并且初始不包含任何边。

评测方式

样例评测库将读入如下格式的输入数据:

第一行包括三个正整数 $n,m$ 和 $\textit{lim}$,分别表示地铁站个数,线路条数和交互限制。

接下来 $m$ 行,每行两个整数 $u_i,v_i$,表示一条线路。

样例评测库将输出如下格式的输出数据:

对于每一组数据,如果你交互过程合法,交互库将输出 SuccessToo many merge,并在第二行输出你调用 merge 的次数,第三行输出你求出的答案,否则会输出 Wrong Answer [id],你可以查阅样例评测库来确定错误类型。

交互式类型的题目怎么本地测试

最终测试中,线路序列是确定的,不会因为你的询问而改变。

样例

input

4 4 1000
1 2
2 3
3 4
4 2

output

Success
Count of merge: 6
3 3 4 4

explanation

以下是一个合法的交互过程。

交互库调用 选手调用 返回 并查集状态
init(4, 4, 1000) $~$ $~$ $(1),(2),(3),(4)$
solve(1) $~$ $~$ $(1),(2),(3),(4)$
$~$ merge(1) $~$ $(1,2),(3),(4)$
$~$ check(2) true $(1,2),(3),(4)$
$~$ merge(2) $~$ $(1,2,3),(4)$
$~$ check(3) true $(1,2,3),(4)$
$~$ merge(3) $~$ $(1,2,3,4)$
$~$ check(4) false $(1,2,3,4)$
solve $~$ 3 $(1,2,3,4)$
solve(2) $~$ $~$ $(1,2,3,4)$
$~$ undo() $~$ $(1,2,3),(4)$
$~$ undo() $~$ $(1,2),(3),(4)$
$~$ undo() $~$ $(1),(2),(3),(4)$
$~$ merge(3) $~$ $(1),(2),(3,4)$
$~$ merge(2) $~$ $(1),(2,3,4)$
$~$ check(4) false $(1),(2,3,4)$
solve $~$ 3 $(1),(2,3,4)$
solve(3) $~$ $~$ $(1),(2,3,4)$
$~$ undo() $~$ $(1),(2),(3,4)$
$~$ check(4) false $(1),(2),(3,4)$
$~$ merge(4) $~$ $(1),(2,3,4)$
solve $~$ 4 $(1),(2,3,4)$
solve(4) $~$ $~$ $(1),(2,3,4)$
solve $~$ 4 $(1),(2,3,4)$

其中 solve 的返回值均在若干行后的,标注着交互库调用 solve 的行。

数据范围与提示

保证若你的交互过程满足题目限制,且 check 次数不超过 $8\times 10^6$,交互库不会占用超过 $\texttt{1s}$ 时间和 $\texttt{32MB}$ 空间。

子任务编号 $n\leq$ $m\leq$ $\textit{lim}\geq$ 特殊性质 分值
$1$ $1000$ $1000$ $10^6$ $10$
$2$ $10^4$ $2\times 10^4$ $5\times 10^6$ $30$
$3$ $10^5$ $2\times 10^5$ $5\times 10^6$ 数据随机 $30$
$4$ $10^5$ $2\times 10^5$ $5\times 10^6$ $30$

对于所有数据,$2\leq n, m,lim \leq 5\times 10^6$。

时间限制:$\texttt{3s}$

空间限制:$\texttt{512MB}$