Submission #535052

#	Time	Username	Problem	Language	Result	Execution time	Memory
535052		new_acc	Bridges (APIO19_bridges)	C++17	13 / 100	3063 ms	7764 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=10;
	set<pair<int,int> >sorted;
	for(int i=1;i<=m;i++) sorted.insert({c[i],i});
	vector<pair<int,int> >aktz;
	for(int i=1;i<=q;i+=p){
		aktz.clear();
		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});
		}
		sort(aktz.begin(),aktz.end());
		reverse(aktz.begin(),aktz.end());
		auto it=sorted.end();
		for(auto u:aktz){
			while(it!=sorted.begin()){
				it--;
				if((*it).fi<u.fi) {it++;break;}
				if(pom[(*it).se]) continue;
				Union(w[(*it).se].fi,w[(*it).se].se,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) 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>=1;j--) pom2[zap[j].b]=0;
		}
		for(int j=1;j<=n;j++) fau[j]=j,siz[j]=1;
		for(int j=i;j<=min(q,i+p-1);j++){
			if(zap[j].a==1) sorted.erase({c[zap[j].b],zap[j].b}),c[zap[j].b]=zap[j].c,sorted.insert({c[zap[j].b],zap[j].b});
			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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27