#P9713. Find a City

    ID: 6339 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>图论贪心数据结构CF1900构造最短路

Find a City

Find a City

题目描述

一个国家有 nn 座城市,任意两座不同城市之间恰有一条单向道路。将城市看作点、道路看作有向边,得到一张竞赛图。

若一个城市的出度至少为 n−2n-2,称它为“好的”城市。你不知道道路的方向,但可以询问两个城市间的道路方向。请在不超过 qq 次询问内找到任意一个好的城市;若不存在,则报告不存在。

接口说明

在程序开头包含头文件:

#include "city.h"

不要实现 main 函数,只需实现:

int solve(int n);

返回一个好的城市的编号;不存在时返回 −1-1。评测程序会多次调用 solve,每次调用时应初始化本次使用的数组和状态。

可以调用的询问函数为:

bool ask(int x, int y);

若道路方向为 x→yx\to y,返回 true(11),否则返回 false(00)。调用时须保证 1≤x,y≤n1\le x,y\le n 且 x≠yx\ne y。每次 solve 调用中的询问次数不能超过对应子任务的 qq。

样例

n=4n=4,六条道路为 1→21\to2、3→13\to1、2→32\to3、1→41\to4、4→24\to2、4→34\to3。

ask(1,2) 返回 11,ask(1,3) 返回 00,ask(1,4) 返回 11。城市 11 的出度为 2=n−22=n-2,因此 solve 可以返回 11。

限制与约定

子任务 分值 nn 上界 ∑n\sum n 上界 每次调用允许的询问数 qq
1 10 100 1000 n(n−1)/2n(n-1)/2
2 20 10610^6 10n10n
3 30 1000 5n5n
4 40 4n4n

所有数据满足 3≤n≤10003\le n\le1000,∑n2≤107\sum n^2\le10^7。求和针对同一测试文件中的所有调用。

题目时间限制为 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!。