求助,并查集做法为什么不行
查看原帖
求助,并查集做法为什么不行
951886
niumachaoren楼主2024/10/12 14:02

想用扩展并查集来进行身高关系的处理,a>b设为在a+k和b之间连边,求助为什么会wa16pts

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
	x=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
}
const int maxn=1e4+10;
int n,k,q,a[maxn],p[maxn],fa[maxn<<1];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
int main(){
	read(n),read(k),read(q);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=2*k;j++)fa[j]=j;
		for(int j=i+1;j<=n;j++){
			int now=((j-i)&1);
			int x=a[j-1],y=a[j];
			if(x==y)break;
			if(now){
				if(find(x)==find(y+k))break;
				merge(x+k,y);
			}
			else{
				if(find(x+k)==find(y))break;
				merge(x,y+k);
			}
			p[i]=j;
		}
//		cout<<p[i]<<'\n';
	}
	while(q--){
		int l,r;
		read(l),read(r);
		if(r<=p[l])cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}
2024/10/12 14:02
加载中...