提出 #68974938

---

ソースコード 拡げる

#include<iostream>
#include<algorithm>
#include<vector>
#define ub upper_bound
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+10;
int n,m,q,f[N],s[N],tim[N];
vector <pii> sp[N];
int finds(int x,int lim) {return tim[x]<=lim?finds(f[x],lim):x;} 
int chk(int x,int lim)
{
	int tp=ub(sp[x].begin(),sp[x].end(),(pii){lim,m})-sp[x].begin()-1;
	return sp[x][tp].se;
}
int check(int x,int y,int lim)
{
	int fx=finds(x,lim),fy=finds(y,lim);
	return fx==fy?chk(fx,lim):chk(fx,lim)+chk(fy,lim);
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i,s[i]=1,tim[i]=m+1,sp[i].pb({0,1});
	for(int i=1;i<=m;i++)
	{
		int u,v,x,y; cin>>u>>v,x=finds(u,m),y=finds(v,m);
		if(x!=y)
		{
			if(s[x]>s[y]) swap(x,y);
			tim[x]=i,s[y]+=s[x],f[x]=y,sp[y].pb({i,s[y]});
		}
	}
	cin>>q;
	while(q--)
	{
		int x,y,z,l=1,r=m,res=m; cin>>x>>y>>z;
		while(l<=r)
		{
			int mid=((l+r)>>1);
			if(check(x,y,mid)>=z) res=mid,r=mid-1;
			else l=mid+1;
		}
		cout<<res<<'\n';
	}
	return 0;
}

提出情報

ジャッジ結果