提出 #68998525

---

ソースコード 拡げる

#include<iostream>
#include<vector>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+10;
const int K=17+5;
const int M=N*K*8;
int n,m,q,cur,f[N],s[N],tu[N],tv[N],tx[N],ty[N],tz[N],res[N],tp[N];
int t,qi[M],pre[M],suf[M],bg[N][K],ed[N][K],px[N],py[N];
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
bool check(int x,int y,int z,int k)
{
	int g=(1<<k),nx=(x/g+1)*g,ny=(y/g+1)*g;
	return (y==-1?nx:nx+ny)<z;
}
void ins(int ti,int k,int i)
{
	qi[++t]=i; int pl=bg[ti][k],pr=suf[pl];
	suf[pl]=t,pre[pr]=t,suf[t]=pr,pre[t]=pl;
}
void del(int p) {suf[pre[p]]=suf[p],pre[suf[p]]=pre[p];}
struct nod{int k,i,f;};
void cle(int ti,int lim)
{
	vector <nod> ta;
	for(int k=0;(1<<k)<=lim;k++)
	{
		int u=suf[bg[ti][k]];
		while(u!=ed[ti][k])
		{
			int i=qi[u],fx=finds(tx[i]),fy=finds(ty[i]);
			if(px[i]) del(px[i]),px[i]=0;
			if(py[i]) del(py[i]),py[i]=0;
			if(fx==fy)
			{
				if(s[fx]>=tz[i]) res[i]=cur;
				else
				{
					while(tp[i]&&!check(s[fx],-1,tz[i],tp[i])) tp[i]--;
					if(fx==ti) ta.pb({tp[i],i,0});
					else ins(fx,tp[i],i),px[i]=t;
				}
			}
			else
			{
				if(s[fx]+s[fy]>=tz[i]) res[i]=cur;
				else
				{
					while(tp[i]&&!check(s[fx],s[fy],tz[i],tp[i])) tp[i]--;
					if(fx==ti) ta.pb({tp[i],i,0});
					else ins(fx,tp[i],i),px[i]=t;
					if(fy==ti) ta.pb({tp[i],i,1});
					else ins(fy,tp[i],i),py[i]=t;
				}
			}
			u=suf[u];
		}
		suf[bg[ti][k]]=ed[ti][k],pre[ed[ti][k]]=bg[ti][k];
	}
	for(nod te:ta)
	{
		ins(ti,te.k,te.i);
		if(te.f) py[te.i]=t;
		else px[te.i]=t;
	}
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		s[i]=1,f[i]=i;
		for(int k=0;k<17;k++)
		{
			bg[i][k]=++t,ed[i][k]=++t;
			pre[ed[i][k]]=bg[i][k],suf[bg[i][k]]=ed[i][k];
		}
	}
	for(int i=1;i<=m;i++) cin>>tu[i]>>tv[i];
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>tx[i]>>ty[i]>>tz[i],tp[i]=0;
		while(check(1,1,tz[i],tp[i])) tp[i]++;
		if(tp[i]) tp[i]--;
		ins(tx[i],tp[i],i),px[i]=t,ins(ty[i],tp[i],i),py[i]=t;
	}
	for(int i=1;i<=m;i++)
	{
		int x=finds(tu[i]),y=finds(tv[i]); cur=i;
		if(x==y) continue;
		if(s[x]>s[y]) swap(x,y);
		int sx=s[x],sy=s[y]; s[x]=s[y]=sx+sy,f[x]=y;
		cle(x,s[x]^sx),cle(y,s[y]^sy);
		for(int i=0;i<17;i++) if(suf[bg[x][i]]!=ed[x][i])
		{
			int ly=bg[y][i],ry=suf[ly],lx=suf[bg[x][i]],rx=pre[ed[x][i]];
			pre[lx]=ly,suf[ly]=lx,pre[ry]=rx,suf[rx]=ry;
		}
	}
	for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
	return 0;
}

提出情報

ジャッジ結果