Submission #1259738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259738		MasterDebater	Bridges (APIO19_bridges)	C++20	100 / 100	1576 ms	28988 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+100];
bool ch[M];
stack<int>st;
int get(int x){
	while(x!=par[x])x=par[x];
	return 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)){
		for(int i=0;i<m;i++)ch[i]=0;
		for(int i=0;i<n;i++)sz[i]=1;
		for(int i=0;i<n;i++)par[i]=i;
		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: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27