Submission #2708557

---

Source Code Expand

#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) //fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

const int N=5e5+50;

struct Query { int x,y,z,id,ans,tg; } q[N];
bool cmpTg(Query a,Query b){return a.tg<b.tg;}
bool cmpId(Query a,Query b){return a.id<b.id;}

int n,m,a[N],b[N],p[N],qn,s[N],oa[N],ob[N],os[N],top;

int find(int x){ return p[x]==x?x:find(p[x]); }

void merge(int u,int v){
	u=find(u),v=find(v);
	Pr("mrege (%d,%d)\n",u,v); 
	if(s[u]>s[v])swap(u,v);
	if(u!=v){
		p[u]=v,s[v]+=s[u];
		oa[top]=u,ob[++top]=v;
	}
}

void solve(int l,int r,int L,int R){
//	Pr("solve [%d,%d] [%d,%d)\n",l,r,L,R);
//	rep(i,l,r)Pr("%d %d %d\n",q[i].x,q[i].y,q[i].z);
//	rep(i,1,n)Pr("s[%d]=%d,p[%d]=%d\n",i,s[i],i,p[i]);   
	assert(!(l<=r&&L>=R));
	if(l>r){
		lop(i,L,R)merge(a[i],b[i]); 
		top=0;
		return ; 
	}
	if(R-L==1){
		rep(i,l,r)q[i].ans=L;
		merge(a[L],b[L]);
		top=0;
		return;
	} 
	int mid=(L+R)>>1;
//	Pr("mid=%d\n",mid); 
	lop(i,L,mid)merge(a[i],b[i]); 
	rep(i,l,r){
		int w=find(q[i].x)==find(q[i].y)?s[find(q[i].x)]:s[find(q[i].x)]+s[find(q[i].y)];
		q[i].tg=w<q[i].z;
	}
	sort(q+l,q+r+1,cmpTg);
	int rb=l;while(rb<=r&&q[rb].tg==0)++rb;
	while(top){
	//	Pr("oa=%d,ob=%d\n",oa[top],ob[top]); 
		p[oa[top]]=oa[top];
		s[ob[top]]-=s[oa[top]];
		--top;
	}
	solve(l,rb-1,L,mid);
	solve(rb,r,mid,R);
}

int main(int argc,char *argv[]){
	//freopen("dat.in","r",stdin); 
	read(n),read(m);
	rep(i,1,m)read(a[i]),read(b[i]); 
	rep(i,1,n)p[i]=i,s[i]=1;
	read(qn); 
	rep(i,1,qn){
		q[i].id=i,read(q[i].x),read(q[i].y),read(q[i].z); 
	}
	solve(1,qn,1,m+1);
	sort(q+1,q+qn+1,cmpId);
	rep(i,1,qn)printf("%d\n",q[i].ans);
	return 0;
}

Submission Info

Judge Result