Submission #1259728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259728		MasterDebater	Bridges (APIO19_bridges)	C++20	14 / 100	1242 ms	26148 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=1e5+10,Q=1e5+10,B=1e3;
int n,m,q,a[M],b[M],w[M],t[Q],x[Q],y[Q],sz[N],par[N],ans[Q];
vector<int>v[B];
bool ch[M];
stack<int>st;
int get(int x){
	if(par[x]==x)return x;
	return par[x]=get(par[x]);
}
void unija(int x,int y){
	x=get(x),y=get(y);
	if(x==y)return;
	if(sz[x]>sz[y])swap(x,y);
	st.push(x);
	sz[y]+=sz[x];
	par[x]=par[y];
	return;
}
void rollback(int x){
	while(st.size()>x){
		int k=st.top();
		st.pop();
		sz[par[k]]-=sz[k];
		par[k]=k;
	}
	return;
}
bool cmp1(int a,int b){
	return w[a]>w[b];
}
bool cmp2(int a,int b){
	return y[a]>y[b];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>w[i],a[i]--,b[i]--;
	cin>>q;
	for(int i=0;i<q;i++)cin>>t[i]>>x[i]>>y[i],x[i]--;
	for(int l=0,r=min(l+B-1,q-1);l<q;l+=B,r=min(q-1,l+B-1)){
		fill(ch,ch+m,0);
		fill(sz,sz+n,1);
		iota(par,par+n,0);
		vector<int>upd,ask,nep;
		for(int i=l;i<=r;i++){
			if(t[i]==1){
				upd.push_back(i);
				ch[x[i]]=1;
			}
			else ask.push_back(i);
		}
		for(int i=0;i<m;i++)if(!ch[i])nep.push_back(i);
		sort(nep.begin(),nep.end(),cmp1);
		sort(ask.begin(),ask.end(),cmp2);
		for(int i=l;i<=r;i++){
			if(t[i]==1)w[x[i]]=y[i];
			else{
				v[i-l].clear();
				for(int j=0;j<upd.size();j++)if(w[x[upd[j]]]>=y[i])v[i-l].push_back(x[upd[j]]);
			}
		}
		int cnt=0;
		for(int i=0;i<ask.size();i++){
			int ind=ask[i];
			while(cnt<nep.size() and w[nep[cnt]]>=y[ind]){
				unija(a[nep[cnt]],b[nep[cnt]]);
				cnt++;
			}
			int sz1=st.size();
			for(int j=0;j<v[ind-l].size();j++)unija(a[v[ind-l][j]],b[v[ind-l][j]]);
			ans[ind]=sz[get(x[ind])];
			rollback(sz1);
		}
	}
	for(int i=0;i<q;i++)if(t[i]==2)cout<<ans[i]<<'\n';
	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27