#1995. 信号网络

    ID: 1995 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4603来源:qoj.ac数据:公开样例拓扑排序

信号网络

信号网络

题目描述

标题: 信号网络 - Problem - QOJ.ac

#21434. 信号网络

Statistics

题目描述

这是一道交互题,仅支持 C++ 提交。

你的实验室里有一套封装好的信号网络,你无法直接查看内部的接线,但可以借助测试仪检测信号。

你需要确定关闭所有节点的顺序。为保证安全,关闭一个节点前,必须先关闭它的所有上游节点。若有多种合法顺序,求字典序最小的一种。

具体的,信号网络有 N 个节点,编号为 0∼N−1,以及 M 条有向导线。每条导线将信号从起点传向终点,保证导线构成的图是一张有向无环图。

每条导线传输信号都需要恰好 1 个单位时间。你可以进行如下测试:

  • 选择两个不相交的节点集合 S,T,二者均可为空。在 S 中的所有节点同时投放信号,并在 T 中的每个节点设置接收口。
  • 选定集合后,信号将沿导线的方向传播。测试仪将在信号投放恰好 1 个单位时间后读取所有接收口,并告诉你是否有至少一个接收口收到信号。

因此,一次测试的结果为真,当且仅当存在 u∈S,v∈T,使得网络中有一条从 u 直接连向 v 的导线。每次测试前,网络中的信号都会被清除;每次测试后,你可以立刻知道结果。

你需要在至多 L 次测试内,确定该网络字典序最小的关闭顺序。

也就是说,你需要求出 0∼N−1 的一个排列 P0,…,PN−1,使得对于每条从 u 连向 v 的导线,u 在排列中的位置都早于 v,并使这个排列的字典序最小。两个不同排列的字典序由它们第一个不同位置上的数决定,该位置上的数较小的排列字典序较小。

实现细节

你不需要也不应当实现 main 函数。你需要引用头文件 circuit.h,并实现下面的函数:

std::vector<int> solve(int N, int L, int c);

其中 N 表示网络的节点数,L 表示当前测试数据允许的测试次数上限,c 表示当前测试数据所属的子任务编号。各子任务的限制见"数据范围"。

这个函数需要返回一个长度为 N 的数组 P,其元素恰好为 0∼N−1,表示网络的字典序最小的关闭顺序。对于每组测试数据,该函数恰好被调用一次。

你可以调用下面的函数进行测试:

bool query(std::vector<int> A);

这个函数对应题目描述中的一次测试。你需要保证 A 的长度为 N,且每个元素都属于 {0,1,2}。对于 0≤i<N:

  • A[i] = 0 表示节点 i 既不投放信号,也不设置接收口;
  • A[i] = 1 表示在节点 i 投放信号,即 i∈S;
  • A[i] = 2 表示在节点 i 设置接收口,即 i∈T。

这个函数返回一个 bool 值,表示测试的结果。若 S 或 T 为空,则返回 false。

对于每组测试数据,query 最多被调用 L 次。

下发的 grader.cpp 仅用于本地测试,其询问接口与正式交互库一致,但实现方式和运行效率可能不同。

测试程序方式

将你的实现保存为 circuit.cpp,可以在本题目录下使用以下命令编译:

g++ grader.cpp circuit.cpp -o circuit -std=c++17 -O2 -static

程序正常结束时,标准输出为你返回的数组,标准错误输出 Queries: Q,其中 Q 表示本组数据的询问次数。测试程序不会自动检查返回数组是否为正确答案,你可以将标准输出与对应答案文件进行比较。若询问参数不合法或询问次数超过上限,测试程序会输出错误提示并立即停止。

测试数据文件及其对应答案文件的格式如下。每份输入只包含一组测试数据。输入数据应当符合题目中的约束条件,否则程序可能无法正常结束。

输入格式

第一行包含四个整数 N,M,L,c,依次表示节点数、导线数、测试次数上限和子任务编号。

接下来 M 行中的第 i+1 行(0≤i<M)包含两个整数 Ui,Vi,表示一条从节点 Ui 连向节点 Vi 的有向导线。

输出格式

答案文件包含一行 N 个整数 P0,…,PN−1,表示网络的字典序最小关闭顺序,也就是 solve 应当返回的数组。

样例

输入:

4 2 40000 1
2 0
0 1

输出:

2 0 1 3

节点 2 必须先于节点 0,节点 0 必须先于节点 1;节点 3 与其他节点之间没有导线。所有合法关闭顺序中字典序最小的是 (2,0,1,3)。

在这个网络中,选择 S={2},T={0} 时,测试结果为 true;选择 S={2},T={1} 时,虽然存在从节点 2 到节点 1 的路径,测试结果仍为 false。

数据范围

本题采用捆绑测试。

子任务编号 N≤ 特殊性质 分值 L= 1 200 无 4 4×104 2 200 无 8 2×104 3 1000 M≤2000 8 2.3×104 4 1000 网络的拓扑序唯一 24 2×104 5 400 无 32 8×104 6 1000 无 24 5×104

对于所有数据,保证:

  • 1≤N≤1000,0≤M≤N(N−1)2,L≥2×104;
  • 1≤c≤6,且 L 及其他限制符合上表中对应子任务的要求;
  • 对于 0≤i<M,有 0≤Ui,Vi<N 且 Ui≠Vi;
  • 任意有序点对之间至多存在一条导线,即不存在重边;
  • 网络为有向无环图。

评分标准

注意:

  • 选手不应该通过非法方式获得交互库的内部信息,或者与标准 IO 进行交互,这种行为视为作弊;
  • 交互库是非自适应的,即网络的接线方式在调用 solve 前就已确定,不会随着测试而改变。

保证在合法情况下,交互库消耗时空分别不超过 1 s、64 MB。

本题首先受到和传统题相同的约束。此外,对于每个子任务,若任意一组数据的返回答案错误、询问参数不合法或询问次数超过上限,则该子任务得 0 分;否则按以下规则计分。

记该子任务中,各组测试数据调用 query 的次数的最大值为 Q,并令 q=Q×10−4。

对于子任务 1,2,3,4,当且仅当 Q≤L 时,获得该子任务的全部分数,否则得 0 分。

对于子任务 5,得分按如下规则计算:

范围 得分 q>8 0 2<q≤8 48−16log2(q) q≤2 32

对于子任务 6,得分按如下规则计算:

范围 得分 q>5 0 2<q≤5 40−8q q≤2 24

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 2 40000 1
2 0
0 1
2 0 1 3