Submission #3221931

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int read(){
	int x=0;
	char ch=getchar();
	while (!isdigit(ch))
		ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int n,m,Q;
int fa[N],size[N],id[N],cur=0;
struct Edge{
	int x,y;
}e[N];
struct Query{
	int x,y,z,ans;
}q[N];
void clear_fa(){
	for (int i=1;i<=n;i++)
		fa[i]=i,size[i]=1;
}
int getf(int x){
	return fa[x]==x?x:fa[x]=getf(fa[x]);
}
void Merge(int x,int y){
	x=getf(x),y=getf(y);
	if (x==y)
		return;
	size[x]+=size[y],fa[y]=x;
}
struct Node{
	int L,R,Q;
	int *id;
	Node(){}
	Node(int a,int b,int *d,int c){
		L=a,R=b,Q=c,id=d;
	}
}s[N<<5];
int head,tail;
int tL[N],cL;
int tR[N],cR;
void Insert(int L,int R,int *id,int Q){
	s[++tail]=Node(L,R,id,Q);
}
int calc(int x,int y){
	x=getf(x),y=getf(y);
	return x==y?size[x]:(size[x]+size[y]);
}
void solve(int L,int R,int *id,int Q){
	if (L>R||Q==0)
		return;
	int mid=(L+R)>>1;
	if (cur>mid)
		clear_fa(),cur=0;
	while (cur<mid)
		cur++,Merge(e[cur].x,e[cur].y);
	cL=cR=0;
	for (int i=1;i<=n;i++){
		int ID=id[i],res=calc(q[ID].x,q[ID].y);
		if (res>=q[ID].z)
			tL[++cL]=ID,q[ID].ans=min(q[ID].ans,mid);
		else
			tR[++cR]=ID;
	}
	for (int i=1;i<=cL;i++)
		id[i]=tL[i];
	for (int i=1;i<=cR;i++)
		id[cL+i]=tR[i];
	Insert(L,mid-1,id,cL);
	Insert(mid+1,R,id+cL,cR);
}
void BFS(int L,int R,int *id,int Q){
	head=tail=0;
	clear_fa();
	Insert(L,R,id,Q);
	while (head<tail)
		head++,solve(s[head].L,s[head].R,s[head].id,s[head].Q);
}
int main(){
	n=read(),m=read();
	for (int i=1;i<=m;i++)
		e[i].x=read(),e[i].y=read();
	Q=read();
	for (int i=1;i<=Q;i++)
		q[i].x=read(),q[i].y=read(),q[i].z=read(),id[i]=i,q[i].ans=m;
	BFS(1,m,id,Q);
	for (int i=1;i<=Q;i++)
		printf("%d\n",q[i].ans);
	return 0;
}

Submission Info

Judge Result