UOJ Logo Universal Online Judge

UOJ

#234. 【IOI2015】Towns

统计

哈萨克斯坦有 $N$ 座⼩城镇,编号从 $0$ 到 $N - 1$,另有不知道具体数量的若⼲⼤城市。哈萨克斯坦的这些⼩城镇和⼤城市统称为定居点。

哈萨克斯坦的所有定居点通过⼀个双向公路⽹络连接在⼀起。每条公路连接 $2$ 个不同的定居点。每对定居点之间最多有⼀条直接相连的公路。对于任意⼀对定居点 $a$ 和 $b$,只要经过的公路最多只能使⽤⼀次,则有⼀条唯⼀的路径从 $a$ ⾛到 $b$。

每个⼩城镇只能与另外⼀个定居点直接相连,⽽⼤城市与 $3$ 个或者更多的定居点直接相连。

下图给出了⼀个由 $11$ 个⼩城镇和 $7$ 个⼤城市组成的⽹络。⼩城镇⽤圆圈表⽰并⽤整数编号,⼤城市⽤⽅形表⽰并⽤字母标识。

样例

每条公路的⻓度都是⼀个正整数。两个定居点之间距离是从⼀个定居点⾛到另⼀个定居点所经过的所有公路⻓度之和的最⼩值。

对于⼤城市 $C$,$r(C)$ 表⽰离 $C$ 最远的⼩城镇到 $C$ 的距离。在所有的⼤城市中 $r(C)$ 值最⼩的⼤城市称为中⼼城市(hub)。离中⼼城市最远的⼩城镇到中⼼城市的距离是 $R$,即 $R$ 是所有 $r(C)$ 的最⼩值。

在上例中,离⼤城市 $a$ 最远的⼩城镇是城镇 $8$,⼤城市 $a$ 和⼩城镇 $8$ 之间的距离 $r(a) = 1 + 4 + 12 = 17$。对于⼤城市 $g$ 来说,$r(g) = 17$(距离⼤城市 $g$ 最远的⼩城镇之⼀是城 $6$)。上图中唯⼀的中⼼城市是城市 $f$,其 $r(f)=16$,因此上例中 $R$ 是 $16$。

删除某个中⼼城市后,整个⽹络会分成⼏个连通⼦图,如果每个⼦图中⾄多包含 $\lfloor N / 2 \rfloor$ 个⼩城镇,那么这个删除的中⼼城市就是平衡的(balanced)。注意:计数中不含⼤城市,$\lfloor x \rfloor$ 表⽰不⼤于 $x$ 的最⼤整数。

在上例中,⼤城市 $f$ 是⼀个中⼼城市,如果删除 $f$,整个⽹络分成 $4$ 个连通⼦图,这 $4$ 个⼦图分别包含下列⼩城镇 ${0, 1, 10}, {2, 3}, {4, 5, 6, 7}$ 和 ${8, 9}$,没有任何⼀个⼦图包含超过 $\lfloor 11 / 2 \rfloor = 5$ 个⼩城镇,所以⼤城市 $f$ 是⼀个平衡的中⼼城市。

任务

最初,整个⽹络的唯⼀信息只有⼩城镇的数⽬ $N$。你不知道⼤城市的数⽬,也不清楚公路的⽹络连接情况。你获取信息的唯⼀⽅法是查询两个⼩镇之间的距离。

你的任务是确定: 在所有的⼦任务中:距离 $R$。 ⼦任务 $3$ 到 $6$:⽹络中是否存在平衡的中⼼城市。

你需要实现函数 hubDistance。Grader 将会在⼀次运⾏中评测多个测试点。每次运⾏时最多有 $40$ 个测试点。对每个测试点,grader 会调⽤你的函数 hubDistance 恰好⼀次。请确保你的函数在每次被调⽤时都初始化所有需要的变量。

  • hubDistance(N, sub)
    • N: ⼩城镇的数⽬。
    • sub: ⼦任务编号(详⻅⼦任务描述部分)。
    • sub是 $1$ 或者 $2$ 时,该函数返回 $R$ 或 $-R$ 均可。
    • sub⼤于 $2$ 时,如果存在平衡的中⼼城市,该函数返回 $R$,否则返回 $-R$。

你的 hubDistance 函数可以通过调⽤ grader 函数 getDistance(i, j) ⽽获得关于公路⽹络的信息。函数 getDistance(i, j) 返回⼩城镇 $i$ 与⼩城镇 $j$ 之间的距离。注意:如果 $i$ 和 $j$ 相同的话,函数的返回值将是 $0$,⽽且当参数不合法时,返回值也是 $0$。

⼦任务

对每个测试点⽽⾔: $N$ 的范围是 $[6, 110]$。 两个⼩镇之间距离的范围是$[1, 1000000]$。

你调⽤ getDistance(i, j) 函数查询的次数是有⼀定限制的。该限制与⼦任务有关,详⻅下表。如果你的程序调⽤的次数超过限制,你的程序将会被终⽌,且视为答案错误。

子任务 分数 查询次数限制 是否查找平衡中心城市 限制
113$\frac{n(n - 1)}{2}$
212$\lceil \frac{7n}{2}\rceil$
313$\frac{n(n - 1)}{2}$
410$\lceil \frac{7n}{2}\rceil$每个大城市都刚好与 $3$ 个定居点连接
513$5n$
639$\lceil \frac{7n}{2}\rceil$

注意:$\lceil x \rceil$ 表⽰⼤于或等于 $x$ 的最⼩整数。

实现细节

你只能提交一个源文件实现如上所述的 hubDistance 函数,并且遵循下面的命名和接口。你需要包含头文件 towns.h。

int hubDistance(int N, int sub);

评测方式

请注意⼦任务的编号也是输⼊的⼀部分。grader 根据⼦任务的编号⽽改变它评分的⽅法。

  • 第 $1$ ⾏:⼦任务编号和测试点的数⽬。
  • 第 $2$ ⾏:$N_1$,第⼀个测试点中⼩城镇的数⽬。
  • 接下来的 $N_1$ ⾏:第 $i$ ⾏($1 \le i \le N_1$)第 $j$ 个($1 \le j \le N_1$)数字是⼩城镇 $i - 1$ 到⼩城镇 $j - 1$ 的距离。
  • 随后是下⼀个测试点的数据,格式与第 $1$ 个测试点的数据相同。

对于每个测试点,grader 会在不同⾏上输出函数 hubDistance 的返回值及调⽤函数的次数。

本题样例的输⼊格式如下:

1 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0

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

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

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

下载

样例及测评库下载