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;
	}
}