CF1514E - Baby Ehab's Hyper Apartment

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

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;
	}
}
上一篇:windows下快速删除node_modules文件


下一篇:ARC114 - Paper Cutting 2