JOI 岛是一个观光胜地,全岛被定为一个自然公园。
JOI 岛有
你和你的朋友 IOI 酱决定考察 JOI 岛。为了考察能够高效进行,你不得不掌握全岛的结构。岛上的诸多动物会带来危险,因此由运动细胞发达的 IOI 酱去探索全岛,而你则负责基于 IOI 酱的报告来确定岛的结构。
你可以对 IOI 酱指定两个广场
请编写一个程序与 IOI 酱交流并确定 JOI 岛的完整结构。由于考察不能持续过长时间,需要将询问次数限制在
实现细节
本题仅支持 C/C++ 语言。
你需要实现一个过程来确定岛的结构。请包含头文件 park.h
。
程序需要实现以下过程。
void Detect(int T, int N)
- 此函数只会被调用
次。 - 参数
表示子任务编号, 表示广场的数目。
- 此函数只会被调用
程序中需要调用以下函数来输出所确定的 JOI 岛的构造。
void Answer(int A, int B)
- 此函数被调用的次数须等于 JOI 岛的道路数目。
- 参数
和 表示确定了一条联结广场 和 的道路。 - 参数需要满足以下条件:
和 须满足 。不满足此条件时,会被判为 Wrong Answer [1]。- 对于一组参数
,广场 与广场 之间须有一条道路。不满足此条件时,会被判为 Wrong Answer [2]。 - 对于一组参数
不得调用 次及以上。不满足此条件时,会被判为 Wrong Answer [3]。
此外,程序中可以调用如下函数。
int Ask(int A, int B, int Place[])
- 此函数用于向 IOI 酱提出询问。
指向表示每个广场是否可以经过的数组。对于每个 ( ), 表示可以经过广场 , 表示不可以经过广场 。- 此函数的返回值在可以只经由允许的广场从广场
到达广场 的情况下返回 ,不能到达的情况下返回 。 - 参数需要满足以下条件:
。 ( )。 。 。
- 不满足这些条件时,会被判为 Wrong Answer [4]。另外,数组
的长度不足 时的行为是未定义的。 - 此外,函数
被调用的次数不能超过 次。超过的情况下,会被判为 Wrong Answer [5]。
函数
为了内部使用而定义的其他函数及全局变量不作限制。但是,你的提交不应该向标准输入/输出或者其他文件进行任何读写操作。
测试程序方式
「附加文件」中提供了 park.h
、grader.c
和 grader.cpp
三个文件。若你编写的程序名称为 park.c
或 park.cpp
,请运行以下命令来编译:
C 语言
gcc -std=c11 -O2 -o grader grader.c park.c -lm
C++ 语言
g++ -std=c++14 -O2 -o grader grader.cpp park.cpp
当命令成功时,会产生一个可执行文件 grader
。
注意实际评测时的程序与下发的样例评测程序并不相同。实际的 park.h
函数实现将通过标准输入/输出与单独运行的交互器进行交互。
样例评测程序输入格式
样例评测程序将从标准输入读入以下数据。
第
行一个整数 ,表示子任务编号。第
行一个整数 ,表示广场有 个。第
行一个整数 ,表示道路有 条。接下来
行中的第 ( )行包含两个空格分隔的整数 ,表示有一条联结广场 与广场 的双向道路。
样例评测程序输出格式
样例评测程序将向标准输出输出以下信息。
判为正确时,输出
Accepted
;运行过程中被判为错误时,以
Wrong Answer [x]
的格式报告并退出。
程序执行过程中违反了多种限制时,只会报告其中的一种。
样例一
input (grader)
1 6 7 0 1 0 3 1 2 1 4 2 4 2 5 3 4
interaction
函数调用 | 返回值 |
---|---|
Ask(3, 5, { 0, 0, 1, 1, 1, 1 }) |
1 |
Answer(2, 4) |
|
Answer(2, 5) |
|
Answer(3, 4) |
|
Ask(0, 4, { 1, 0, 1, 0, 1, 0 }) |
0 |
Answer(0, 1) |
|
Answer(0, 3) |
|
Answer(1, 4) |
|
Answer(1, 2) |
注意本样例中的函数调用可能并无实际意义。
本样例中,函数
本样例中,JOI 岛的结构如下图所示。
第
次调用函数 时,允许经过广场 ,询问从广场 是否可以到达广场 。由于可以到达,函数 返回 。第
次调用函数 时,允许经过广场 ,询问从广场 是否可以到达广场 。由于不可以到达,函数 返回 。
数据范围与提示
所有数据满足下列条件。
。 。 。对于任意一个广场,至多有
条道路将它与其他广场联结。对于任意两个不同广场,可以通过若干道路互相到达。
对于任意两个不同广场,联结它们的道路至多有
条。
子任务数据满足下列条件。
子任务 1(10 分)
。 。
子任务 2(10 分)
。 。对于广场
与广场 ,只有 条道路将它们与其他广场相连。对于其他广场,恰有 条道路将它们与其他广场相连。
子任务 3(27 分)
。 。对于任意一个
( ),至多经由 个其他广场即可从广场 到达广场 。
子任务 4(30 分)
。 。
子任务 5(23 分)
。
时间限制:
空间限制: