提出 #68975327

---

ソースコード 拡げる

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,q,pos,ct,f[N],s[N],tu[N],tv[N],res[N];
struct ask{int x,y,z,id;}a[N],b[N];
struct nod{int l,r,ql,qr;}c[N],d[N];
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
void merg(int tim)
{
	int x=finds(tu[tim]),y=finds(tv[tim]);
	if(x!=y)
	{
		if(s[x]>s[y]) swap(x,y);
		s[y]+=s[x],f[x]=y;
	}
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>tu[i]>>tv[i];
	cin>>q,c[ct=1]={1,m,1,q};
	for(int i=1;i<=q;i++) cin>>a[i].x>>a[i].y>>a[i].z,a[i].id=i;
	while(ct)
	{
		int tp=0,cd=0;
		for(int i=1;i<=n;i++) f[i]=i,s[i]=1;
		for(int i=1;i<=ct;i++)
		{
			int l=c[i].l,r=c[i].r,ql=c[i].ql,qr=c[i].qr;
			if(l==r) {for(int j=ql;j<=qr;j++) res[a[j].id]=l; continue;}
			if(ql>qr) continue;
			int mid=((l+r)>>1),pl=ql,pr=qr;
			while(tp<mid) merg(++tp);
			for(int j=ql;j<=qr;j++)
			{
				int x=finds(a[j].x),y=finds(a[j].y);
				if((x==y?s[x]:s[x]+s[y])>=a[j].z) b[pl++]=a[j];
				else b[pr--]=a[j];
			}
			for(int j=ql;j<=qr;j++) a[j]=b[j];
			d[++cd]={l,mid,ql,pl-1},d[++cd]={mid+1,r,pr+1,qr};
		}
		ct=cd;
		for(int i=1;i<=ct;i++) c[i]=d[i];
	}
	for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
	return 0;
}

提出情報

ジャッジ結果