Submission #1138886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138886		Rawlat_vanak	Bridges (APIO19_bridges)	C++20	100 / 100	1734 ms	16720 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back

struct changes{
	int a; int b; int si;
	changes(int _a, int _b, int _s): a(_a),b(_b),si(_s){}
};

const int block=1000;

vector<pair<pii,pii>> edges; //weight, index, u,v
set<pair<pii,pii>> edges2;
vector<pair<int,pii>> realedges;
vector<int> sz,parent;
stack<changes> roll;


int find(int u){
	while(u!=parent[u]) u=parent[u];
	return u;
}

void unite(int a, int b){
	a=find(a);b=find(b);
	if(sz[a]<sz[b]) swap(a,b);
	int tmp=sz[a];
	if(a!=b){
		parent[b]=a;
		sz[a]+=sz[b];
	}
	roll.push({a,b,tmp});

}

void rollback(){
	if(roll.empty()) return;
	int a=roll.top().a;
	int b=roll.top().b;
	int si=roll.top().si;
	roll.pop();
	parent[b]=b;
	sz[a]=si;

}

int32_t main(){
	speedIO;
	int t,n,m,k,q;
	//cin>>t;
	t=1;
	while(t--){
		cin>>n>>m;
		parent.clear();
		parent.resize(n+1);
		sz.clear();
		sz.resize(n+1,1);
		for(int i=0;i<=n;i++){
			parent[i]=i;
		}
		vector<int> u(m+1),v(m+1),d(m+1);
		for(int i=1;i<=m;i++){
			cin>>u[i]>>v[i]>>d[i];
		
		}
		cin>>q;
		vector<int> type(q+1),x(q+1),y(q+1),answer(q+1,-1);
		for(int i=1;i<=q;i++){
			cin>>type[i]>>x[i]>>y[i];
		}
	
		for(int toobad=1;toobad<=q;toobad+=block){
			vector<bool> blocked(m+1,false);
			vector<pair<pii,int>> calc,bad;
			vector<vector<pii>> badder(m+1,vector<pii>());// s,w;
			for(int j=toobad;j<min(toobad+block,q+1);j++){// setting up
				if(type[j]==1){
					
					bad.pb({{x[j],y[j]},j});
					//bad.pb({{x[j],d[x[j]]},0});
					if(!blocked[x[j]]){
						badder[x[j]].pb({d[x[j]],0});
					}
					badder[x[j]].pb({y[j],j});
					blocked[x[j]]=true;
				}else{
					calc.pb({{y[j],x[j]},j});
				}
			}
			/*for(auto blah:bad){
				cout<<blah.f.f<<' '<<blah.f.s<<' '<<blah.s<<'\n';
			}
			cout<<"break\n";
			for(auto blah:calc){
				cout<<blah.f.f<<' '<<blah.f.s<<' '<<blah.s<<'\n';
			}*/
			vector<pii> eeedges;
			for(int i=1;i<=m;i++){
				if(blocked[i]) continue;
				eeedges.pb({d[i],i});
			}
			

			sort(eeedges.rbegin(),eeedges.rend());
			sort(calc.rbegin(),calc.rend());
			iota(parent.begin()+1,parent.end(),1);
			fill(sz.begin()+1,sz.end(),1);
			roll=stack<changes>();
			int index=0;
			


			for(auto bao:calc){
				int weight=bao.f.f;
				int start=bao.f.s;
				int tm=bao.s;
				
				//cout<<"hi "<<start<<' '<<weight<<' '<<tm<<'\n';
				// adding orignal edges
				while(index<eeedges.size() and eeedges[index].f>=weight){
					unite(u[eeedges[index].s],v[eeedges[index].s]);
					//cout<<"adding "<<u[eeedges[index].s]<<' '<<v[eeedges[index].s]<<'\n';
					index++;
				}

				//added bad edges
				int cnt=0;
				/*for(auto wao:bad){
					int idx=wao.f.f;
					int r=wao.f.s;
					int badtm=wao.s;

					cout<<idx<<' '<<r<<' '<<badtm<<'\n';
					if(badtm<tm and r>=weight){
						unite(u[idx],v[idx]);
						cout<<"adding bad "<<u[idx]<<' '<<v[idx]<<'\n';
						cnt++;
					}

				}*/

				for(auto i:bad){
					int wao=i.f.f;
					int timepass=badder[wao].size()-1;
					//cout<<"why "<<timepass<<'\n';
					while(badder[wao][timepass].s>tm){
						timepass--;
					}
					if(timepass==-1) continue;
					int r=badder[wao][timepass].f;
					if(r>=weight){
						unite(u[wao],v[wao]);
						//cout<<"adding bad "<<u[wao]<<' '<<v[wao]<<'\n';
						cnt++;
					}
				}

				answer[tm]=sz[find(start)];
				while(cnt>0){
					rollback();
					cnt--;
				}

			}

			//updating
			for(auto i:bad){
				int kao=i.f.f;
				int zao=i.f.s;
				d[kao]=zao;
			}


		}


		for(int i:answer){
			if(i!=-1){
				cout<<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