Submission #296321

#	Time	Username	Problem	Language	Result	Execution time	Memory
296321		AMO5	Bridges (APIO19_bridges)	C++17	30 / 100	3014 ms	107664 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int,int>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define eb emplace_back

const int mxn = 5e4+5;
const int mxm = 1e5+5;
const int sqn = 650;

int n,m,qq;
int lw[mxm],las[mxm],W[mxn],ans[mxm];
pair<int,ii>q[mxm];
ii ed[mxm];

struct edge{
	int u,v,w,ql,qr;
	edge(int uu, int vv, int ww, int le, int ri){
		u=uu, v=vv, w=ww, ql=le, qr=ri;
	}
	bool operator < (const edge &rhs)const{
		return w>rhs.w;
	}
};

vector<edge>edges;
//DSU
int par[mxn],siz[mxn];

void init(){
	for(int i=1; i<=n; i++){
		par[i]=i;
		siz[i]=1;
	}
	return;
}

int rt(int u, bool cmps){
	if(u==par[u])return u;
	else{
		if(cmps){
			par[u]=rt(par[u],cmps);
			return par[u];
		}else{
			return rt(par[u],cmps);
		}
	}
}
vector<pair<int,ii>>updates;
void merge(int u, int v, bool cmps){
	//cerr<<"merging "<<u<<" "<<v<<" "<<cmps<<"\n";
	u=rt(u,cmps); v=rt(v,cmps);
	if(u==v){
		return;
	}
	if(siz[u]<siz[v])swap(u,v);
	updates.eb(v,ii(par[v],siz[v]));
	par[v]=u;
	siz[u]+=siz[v];
	return;
}

void rollback(){
	if(updates.empty())return;
	int v=updates.back().fi;
	int pv=updates.back().se.fi;
	int sv=updates.back().se.se;
	updates.pop_back();
	if(v==-1)return;
	int curp = par[v];
	siz[curp] -= sv;
	par[v]=pv;
	return;
}

void solve(int l, int r){
	init();
	vector<pair<int,ii>>q1,q2;
	vector<int>bad;
	for(int i=l; i<=r; i++){
		if(q[i].fi==1){
			bad.eb(q[i].se.fi);
			q1.eb(i,q[i].se);
		}else{
			q2.eb(q[i].se.se,ii(i,q[i].se.fi));
			//sort according to weight
		}
	}
	sort(q2.rbegin(),q2.rend());
	int ptr=0;
	//cerr<<sz(q2)<<" "<<l<<" "<<r<<"\n";
	for(int i=0; i<sz(q2); i++){
		int curw = q2[i].fi;
		int ind = q2[i].se.fi;
		int st = q2[i].se.se; //point
		while(ptr<sz(edges)&&curw<=edges[ptr].w){
			if(edges[ptr].ql<=l&&edges[ptr].qr>=r)
				merge(edges[ptr].u,edges[ptr].v,1);
			ptr++;
		}
		vector<ii>upd;
		int ptrq1 = 0;
		while(ptrq1<sz(q1)&&q1[ptrq1].fi<=ind){
			int eind = q1[ptrq1].se.fi;
			int ww = q1[ptrq1].se.se;
			//cerr<<q1[ptrq1].fi<<" "<<eind<<" set "<<ww<<"\n";
			upd.eb(eind,W[eind]);
			W[eind]=ww;
			ptrq1++;
		}
		//later need to rollback [changes b4 current ind]
		/*
		for(int i=1; i<=m; i++){
			cerr<<ed[i].fi<<" "<<ed[i].se<<" "<<W[i]<<"\n";
		}
		*/ 
		int cur = sz(updates);
		for(int eind:bad){
			//cerr<<eind<<" "<<W[eind]<<"\n";
			if(W[eind]>=curw){
				//cerr<<W[eind]<<" ";
				merge(ed[eind].fi,ed[eind].se,0);
			}
		}
		/*
		cerr<<i<<": "<<curw<<" "<<ind<<" "<<st<<"\n";
		for(int j=1; j<=n; j++){
			cerr<<j<<" "<<par[j]<<" "<<siz[j]<<"\n";
		}
		// */ 
		ans[ind]=siz[rt(st,0)];
		while(sz(updates)!=cur){
			rollback();
		}
		reverse(upd.begin(),upd.end());
		for(ii x:upd)W[x.fi]=x.se;
	}
	for(auto x:q1){
		W[x.se.fi]=x.se.se;
	}
}

int main(){
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	int u,v,w;
	for(int i=1; i<=m; i++){
		cin>>u>>v>>w;
		W[i]=lw[i]=w;
		ed[i]={u,v};
	}
	cin>>qq;
	for(int i=0; i<qq; i++){
		cin>>q[i].fi>>q[i].se.fi>>q[i].se.se;
		if(q[i].fi==1){
			int eind=q[i].se.fi;
			w=q[i].se.se;
			if(las[eind]<i){
				edges.eb(ed[eind].fi,ed[eind].se,lw[eind],las[eind],i-1);
			}
			las[eind]=i;
			lw[eind]=w;
		}
	}
	for(int i=1; i<=m; i++){
		if(las[i]<=qq-1){
			edges.eb(ed[i].fi,ed[i].se,lw[i],las[i],qq-1);
		}
	}
	sort(edges.begin(),edges.end());
	/*
	for(int i=0; i<sz(edges); i++){
		cerr<<edges[i].w<<" "<<edges[i].u<<" "<<edges[i].v<<" "<<edges[i].ql<<" "<<edges[i].qr<<"\n";
	}
	// */ 
	int ql = 0, qr = 0;
	int sqcnt = 0;
	while(qr<qq){
		if(q[qr].fi==1)sqcnt++;
		if(sqcnt>=sqn){
			solve(ql,qr);
			ql=qr+1;
			sqcnt=0;
		}
		qr++;
	}
	if(ql<qr)solve(ql,qr-1);
	for(int i=0; i<qq; i++){
		if(q[i].fi==2)cout<<ans[i]<<"\n";
	}
	return 0;
}

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