CF1514E - Baby Ehab's Hyper Apartment

Posted on Edited on In

CF1514E - Baby Ehab's Hyper Apartment

题目大意

交互题，给定 \(n\) 元竞赛图，方向未知，通过两种操作

1.查询 \((a,b)\) 方向 ，上限 \(9n\) 次

2.查询 \(a\) 到达一个集合 \(S\) 是否存在正向边，上限 \(2n\) 次

判定所有点之间能否互相到达



分析

能否互相到达是一个强连通问题，因此需要求出分量以及分量之间的拓扑关系

由于是竞赛图，最终的每个分量一定可以排成一排，只能由前面向后面连边

由于 \(9\approx \log n\) ，我们需要一个带 \(\log\) 的算法

考虑将分量内部相对顺序随意，其他关系按照拓扑序确定

通过一个 伪排序 得到一个初始序列

然后只需要合并得到强连通分量的区间

具体的，按照序列顺序，顺次向图上加入每个点 \(i\)

对于每个点 \(i\) 和当前的其所在分量 \(A\) ，左边的分量 \(B\) ，以及左边所有点的集合 \(S\)

判断 \(A,B\) 是否合并，即判断 \(i\) 是否有到达 \(S\) 的边

最多有 \(n-1\) 次合并，以及 \(n-1\) 次合并失败

tips: 由于标准库实现的原因，伪排序不能用std::sort，但是可以用std::stable_sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

const int N=2e5+10;

int n;

int Que(int a,int b){
	printf("1 %d %d\n",a,b),fflush(stdout);
	return rd();
}
int P[N];
int L[N],F[N];

int main(){
	rep(_,1,rd()) {
		n=rd();
		rep(i,0,n-1) F[i]=P[i]=i;
		stable_sort(P,P+n,Que);
		rep(i,0,n-1) {
			L[i]=i;
			while(L[i]) {
				printf("2 %d %d ",P[i],L[i]);
				rep(j,0,L[i]-1) printf("%d ",P[j]);
				puts(""),fflush(stdout);
				if(rd()) L[i]=L[L[i]-1];
				else break;
			}
			rep(j,L[i],i) F[P[j]]=i;
		}
		puts("3");
		rep(i,0,n-1) {
			rep(j,0,n-1) putchar((F[i]<=F[j])+'0');
			puts("");
		}
		fflush(stdout);
		if(rd()==-1) break;
	}
}