Submission #7909452

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int fa[200010];
int hd(int x){return fa[x]==x?x:fa[x]=hd(fa[x]);}
int W[200010],siz[200010],FA[200010],cnt;
int st[18][200010];
int Calc(int a,int b,int w){
	for(int i=17;~i;--i)if(st[i][a]&&W[st[i][a]]<=w)a=st[i][a];
	for(int i=17;~i;--i)if(st[i][b]&&W[st[i][b]]<=w)b=st[i][b];
	return a==b?siz[a]:siz[a]+siz[b];
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),a,b,m=gi();
	for(int i=1;i<=n*2;++i)fa[i]=i;
	for(int i=1;i<=n;++i)siz[i]=1;
	cnt=n;
	for(int i=1;i<=m;++i){
		a=hd(gi()),b=hd(gi());
		if(a==b)continue;
		fa[a]=fa[b]=FA[a]=FA[b]=++cnt;
		siz[cnt]=siz[a]+siz[b];
		W[cnt]=i;
	}
	for(int i=1;i<=n*2;++i)st[0][i]=FA[i];
	for(int i=1;i<18;++i)
		for(int j=1;j<=cnt;++j)
			st[i][j]=st[i-1][st[i-1][j]];
	int Q=gi(),z;
	while(Q--){
		a=gi(),b=gi();z=gi();
		int l=1,r=m,mid;
		while(l<r){
			mid=(l+r)>>1;
			if(Calc(a,b,mid)>=z)r=mid;
			else l=mid+1;
		}
		printf("%d\n",l);
	}
	return 0;
}

Submission Info

Judge Result