Submission #535071

#	Time	Username	Problem	Language	Result	Execution time	Memory
535071		new_acc	Bridges (APIO19_bridges)	C++14	100 / 100	2029 ms	9340 KiB

bridges

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
struct st{
	int a,b,c;
};
int fau[N],siz[N],c[N],res[N];
pair<int,int>w[N];
bitset<N>pom;
bitset<N>pom2;
vi roolf;
st zap[N];
int Find(int a){
	while(fau[a]!=a) a=fau[a];
	return a;
}
void Union(int a,int b,bool xd){
	a=Find(a),b=Find(b);
	if(a==b) return;
	if(siz[a]>siz[b]) swap(a,b);
	fau[a]=b,siz[b]+=siz[a];
	if(xd) roolf.push_back(a);
}
void rollback(){
	while(roolf.size()){
		int u=roolf.back();
		roolf.pop_back();
		siz[fau[u]]-=siz[u];
		fau[u]=u;
	}
}	
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) fau[i]=i,siz[i]=1;
	for(int i=1;i<=m;i++) cin>>w[i].fi>>w[i].se>>c[i];
	int q;
	cin>>q;
	for(int i=1;i<=q;i++) cin>>zap[i].a>>zap[i].b>>zap[i].c;
	int p=1000;
	for(int i=1;i<=q;i+=p){
		vector<pair<int,int> >sorted;
		vector<pair<int,int> >aktz;
		for(int j=i;j<=min(q,i+p-1);j++){
			if(zap[j].a==1) pom[zap[j].b]=1;
			else aktz.push_back({zap[j].c,j});
		}
		for(int j=1;j<=m;j++){
			if(pom[j]) continue;
			sorted.push_back({c[j],j});
		}
		sort(sorted.begin(),sorted.end());
		sort(aktz.begin(),aktz.end(),[](pair<int,int> a,pair<int,int> b){return a>b;});
		int wsk=sorted.size()-1;
		for(auto u:aktz){
			while(wsk>=0 and sorted[wsk].fi>=u.fi) Union(w[sorted[wsk].se].fi,w[sorted[wsk].se].se,0),wsk--;
			int ile=0;
			for(int j=u.se-1;j>=i;j--){
				if(zap[j].a==2 or pom2[zap[j].b]) continue;
				pom2[zap[j].b]=1;
				if(zap[j].c>=u.fi) Union(w[zap[j].b].fi,w[zap[j].b].se,1);
			}	
			for(int j=u.se+1;j<=min(q,i+p-1);j++){
				if(zap[j].a==2 or pom2[zap[j].b]) continue;
				if(c[zap[j].b]>=u.fi) ile++,Union(w[zap[j].b].fi,w[zap[j].b].se,1);
			}
			res[u.se]=siz[Find(zap[u.se].b)];
			rollback();
			for(int j=u.se-1;j>=i;j--) pom2[zap[j].b]=0;
		}
		for(int j=1;j<=n;j++) fau[j]=j,siz[j]=1;
		roolf.clear();
		for(int j=i;j<=min(q,i+p-1);j++){
			if(zap[j].a==1) c[zap[j].b]=zap[j].c;
			pom[zap[j].b]=0;
		}
	}
	for(int i=1;i<=q;i++) if(zap[i].a==2) cout<<res[i]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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