loj#P3173. 「IOI2017」西默夫

「IOI2017」西默夫

题目描述

很抱歉,由于技术局限,本题仅支持各版本 C++.

提示:请参考选手目录下的示例代码,int[] 的实际实现方式为 std::vector<int>

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

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

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

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

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

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

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

实现细节

你需要实现下面的函数:

int[] find_roads(int n, int[] u, int[] v)
  • nn:城市的数量,

  • uuvv:均为长度为 mm 的数组。对于所有 0im10 \le i \le m-1u[i]u[i]v[i]v[i] 是被道路 ii 所连接的城市。

  • 该函数需要返回一个长度为 n1n-1 的数组,其中包括了所有御道的标号(可以以任意的顺序给出)。

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

int count_common_roads(int[] r)
  • rr:长度为 n1n-1 的数组,其中包括了一个黄金集合中的道路标号(可以以任意的顺序给出)。

  • 该函数将返回 rr 中的御道数量。

例子

find_roads(4, [0, 0, 0, 1, 1, 2], [1, 2, 3, 2, 3, 3])

IOI2017-simurgh-desc.png

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

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

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

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

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

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

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

限制条件

  • 2n5002 \le n \le 500
  • n1mn(n1)/2n-1 \le m \le n(n-1)/2
  • 0u[i],v[i]n10 \le u[i], v[i] \le n-1(对于所有 0im10 \le i \le m-1
  • 对于所有 0im10 \le i \le m-1,道路 ii 连接两个不同的城市(即 u[i]v[i]u[i] \ne v[i])。
  • 每对城市之间至多连有一条道路。
  • 经由这些道路,可以在任意一对城市之间来往。
  • 所有的御道组成一个黄金集合。
  • find_roads 可以调用 count_common_roads 最多 qq 次。在每次调用中,由 rr 所给出的道路必须是一个黄金集合。

子任务

  1. 1313 分)n7n\le7 q=30000q=30000
  2. 1717 分)n50n\le50 q=30000q=30000
  3. 2121 分)n240n\le240q=30000q=30000
  4. 1919 分)q=12000q=12000,在任意两个城市之间都连有一条道路
  5. 3030 分)q=8000q=8000

评测工具示例

评测工具示例将读入下述格式的输入数据:

  • 11 行:n mn~m
  • 2+i2+i 行(对于所有 0im10 \le i \le m-1):u[i] v[i]u[i]~v[i]
  • 2+m2+m 行:s[0] s[1]  s[n2]s[0]~s[1]~\cdots~s[n-2]

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

如果 find_roads 最多调用 count_common_roads3000030000 次,而且正确地返回了御道的集合,评测工具示例将会输出 YES。否则评测工具示例将会输出 NO

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

技术提示

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