#P9713. Find a City
Find a City
Find a City
题目描述
一个国家有 座城市,任意两座不同城市之间恰有一条单向道路。将城市看作点、道路看作有向边,得到一张竞赛图。
若一个城市的出度至少为 ,称它为“好的”城市。你不知道道路的方向,但可以询问两个城市间的道路方向。请在不超过 次询问内找到任意一个好的城市;若不存在,则报告不存在。
接口说明
在程序开头包含头文件:
#include "city.h"
不要实现 main 函数,只需实现:
int solve(int n);
返回一个好的城市的编号;不存在时返回 。评测程序会多次调用 solve,每次调用时应初始化本次使用的数组和状态。
可以调用的询问函数为:
bool ask(int x, int y);
若道路方向为 ,返回 true(),否则返回 false()。调用时须保证 且 。每次 solve 调用中的询问次数不能超过对应子任务的 。
样例
,六条道路为 、、、、、。
ask(1,2) 返回 ,ask(1,3) 返回 ,ask(1,4) 返回 。城市 的出度为 ,因此 solve 可以返回 。
限制与约定
| 子任务 | 分值 | 上界 | 上界 | 每次调用允许的询问数 |
|---|---|---|---|---|
| 1 | 10 | 100 | 1000 | |
| 2 | 20 | |||
| 3 | 30 | 1000 | ||
| 4 | 40 |
所有数据满足 ,。求和针对同一测试文件中的所有调用。
题目时间限制为 3 秒,空间限制为 512 MB;评测交互库本身的运行时间不超过 1 秒,空间不超过 128 MB。
本地测试文件
将函数实现保存为 foo.cc,与以上文件放在同一目录,使用 g++ foo.cc implementer.cpp -o city -std=c++17 -O2 编译。交互库从标准输入读取测试,格式为:第一行为调用次数,每次调用先读 n q,再按 (1,2),(1,3),…,(n-1,n) 的次序读入道路方向的 01 字符,1 表示较小编号指向较大编号。全部调用的返回值和询问次数都正确时输出 Accepted!。