UOJ Logo Universal Online Judge

UOJ

#324. 【IOI2017】Simurgh

附件下载 统计

根据沙纳玛(Shahnameh)中的古代波斯传说,Zal,传奇的波斯英雄,疯狂地爱上了 Kabul 王国的公主 Rudaba。在 Zal 向 Rudaba 求婚时,Rudaba 的父亲给他了一个挑战。

在波斯有 $n$ 个城市,标记为从 $0$ 到 $n-1$,以及 $m$ 条双向道路,标记为从 $0$ 到 $m-1$。每条道路连接两个不同的城市。每一对城市至多会被一条道路连接。有些道路是御道(royal roads),专用于皇室行驶,但这是保密的。Zal 的任务是找出哪些道路是御道。

Zal 有一张包括所有城市和所有道路的波斯地图。他不知道哪些道路是御道,但是他可以求救于 Simurgh——好心的神鸟、Zal 的保护者。然而,Simurgh 并不想直接告诉他哪些道路是御道。作为替代,Simurgh 告诉 Zal,所有御道的集合是一个黄金集合(golden set)。一个道路的集合是黄金集合,当且仅当:

  • 它恰好包含 $n-1$ 条道路,而且
  • 对于每一对城市,仅沿着这个集合中的道路即可从其中一个城市抵达另外一个城市。

此外,Zal 可以问 Simurgh 一些问题。对于每个问题:

  1. Zal 选出道路的一个黄金集合,然后
  2. Simurgh 会告诉 Zal,在所选择的黄金集合中有多少条道路是御道。

你的程序可以问 Simurgh 最多 $q$ 个问题,以此帮助 Zal 找出御道的集合。评测工具将扮演 Simurgh 的角色。

实现细节

本题只支持C++。

你需要实现下面的函数:

 std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
  • $n$:城市的数量,
  • $u$ 和 $v$:均为长度为 $m$ 的数组。对于所有 $0\leq i\leq m-1$,$u[i]$ 和 $v[i]$ 是被道路 $i$ 所连接的城市。
  • 该函数需要返回一个长度为 $n-1$ 的数组,其中包括了所有御道的标号(可以以任意的顺序给出)。

你的程序至多只能调用评测工具中的如下函数 $q$ 次:

 int count_common_roads(std::vector<int> r)
  • $r$:长度为 $n-1$ 的数组,其中包括了一个黄金集合中的道路标号(可以以任意的顺序给出)。
  • 该函数将返回 $r$ 中的御道数量。

例子

评测工具调用 find_roads(4, [0, 0, 0, 1, 1, 2], [1, 2, 3, 2, 3, 3])

例子

这个例子中有 $4$ 个城市和 $6$ 条道路。我们将连接城市 $a$ 和 $b$ 的道路表示为 $(a,b)$。这些道路按照下面的顺序被标为从 $0$ 到 $5$:$(0,1)$,$(0,2)$,$(0,3)$,$(1,2)$,$(1,3)$ 和 $(2,3)$。每个黄金集合包含 $n-1=3$ 条道路。

假设御道是标号为 $0$,$1$ 和 $5$ 的道路,即 $(0,1)$,$(0,2)$ 和 $(2,3)$。这样的话:

count_common_roads([0, 1, 2]) 返回 $2$。该询问涉及到标号为 $0,1$ 和 $2$ 的道路,即 $(0,1)$,$(0,2)$ 和 $(0,3)$。其中有两条道路是御道。

count_common_roads([5, 1, 0]) 返回 $3$。该询问涉及到所有的御道。

函数 find_roads 需要返回 $[5,1,0]$ 或任意其他包含这三个元素且长度为 $3$ 的数组。

注意,下面列出的调用是不允许的:

  • count_common_roads([0, 1]):这里 $r$ 的长度不是 $3$。

  • count_common_roads([0, 1, 3]):这里 $r$ 不是一个黄金集合,因为无法仅沿道路 $(0,1)$,$(0,2)$,$(1,2)$ 就从城市 $0$ 走到城市 $3$。

数据范围

  • $2\leq n\leq 500$
  • $n-1\leq m\leq n(n-1)/2$
  • $0\leq u[i],v[i]\leq n-1$(对于所有 $0\leq i\leq m-1$)
  • 对于所有 $0\leq i\leq m-1$,道路 $i$ 连接两个不同的城市(即 $u[i]\neq v[i]$)。
  • 每对城市之间至多连有一条道路。
  • 经由这些道路,可以在任意一对城市之间来往。
  • 所有的御道组成一个黄金集合。
  • find_roads 可以调用 count_common_roads 最多 $q$ 次。在每次调用中,由 $r$ 所给出的道路必须是一个黄金集合。
子任务编号 $n\leq$ $q=$ 特殊性质 分值
$1$ $7$ $30000$ $13$
$2$ $50$ $17$
$3$ $240$ 在任意两个城市之间都连有一条道路 $21$
$4$ $500$ $12000$ $19$
$5$ $8000$ $30$

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

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

评分程序样例

评分程序样例将读入下述格式的输入数据:

  • 第 $1$ 行:$n\ m$
  • 第 $2+i$ 行(对于所有 $0\leq i\leq m-1$):$u[i]\ v[i]$
  • 第 $2+m$ 行:$s[0]\ s[1]\ \cdots\ s[n-2]$

这里 $s[0],s[1],\ldots,s[n-2]$ 是所有御道的标号。

如果 find_roads 最多调用 count_common_roads 了 $30000$ 次,而且正确地返回了御道的集合,评分程序样例将会输出 YES。否则评分程序样例将会输出 NO

需要明确的是,评分程序样例中的函数 count_common_roads 不会检查 $r$ 是否满足一个黄金集合的所有条件。替代性地,它会对数组 $r$ 中的御道进行计数,并且返回。然而,在你提交的程序调用 count_common_roads 时,如果传给它的不是对应某个黄金集合的标号集合,评测结果将会是 Wrong Answer

hack

hack 时,数据格式与上述类似,但是您需要在第 $1$ 行最后额外添加询问次数限制 $q$,这里要求 $q\in \{8000,12000,30000\}$。

技术提示

出于效率方面的考虑,函数 count_common_roads 使用了传引用调用(call by reference)的方式。你可以与平常一样调用这个函数。评测工具确保不会改变 $r$ 中的值。

下载

样例数据与样例评测库下载