Submission #1277685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277685		WH8	Bridges (APIO19_bridges)	C++20	73 / 100	1802 ms	56520 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
const int blk=1000;
int n,m,q;
vector<int> sz(50005, 1), p(50005, 0), res(100001, 0), whendone(50005, 0);
int u[100001], v[100001], w[100001];
int t[100001], x[100001], y[100001];
vector<vector<int>> al(50005);
bool changed[100001];
vector<bool> vis(50005, 0);
int par(int x){
	if(p[x]==0)return x;
	return p[x]=par(p[x]);
}
void merge(int x, int y){
	int a=par(x), b=par(y);
	if(a==b)return;
	p[a]=b;
	sz[b]+=sz[a];
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
	int q;cin>>q;
	for(int i=1;i<=q;i++)cin>>t[i]>>x[i]>>y[i];
	for(int l=1;l<=q;l+=blk){
		int r=min(q+1, l+blk); // answer [l, r) queries. 
		//reset
		fill(changed, changed+m+1, false);
		fill(p.begin(),p.end(), 0);
		fill(sz.begin(),sz.end(), 1);
// weight, type, position, 
// 20, unchanged 0, edge index. 
// 19, query 1, query position. 
// loop through the current block changed before query position. 
// and add to adj list
// dfs from head of current guy. 
// rollback additions to adj list
		vector<tuple<int,int,int>> ev;

		for(int i=l;i<r;i++){
			if(t[i]==1){
				changed[x[i]]=true;
			}
			else ev.pb({y[i], 0, i}); 
		}
		
		for(int i=1;i<=m;i++){
			if(!changed[i])ev.pb({w[i], 1, i});
		}
		sort(ev.begin(),ev.end(),greater<tuple<int,int,int>>());
		for(auto [cw, type, ind]: ev){
			if(type==1){
				merge(u[ind], v[ind]);
			}
			else {
				//~ printf("answering %lld %lld query index is %lld\n", cw, type, ind);
				//~ for(int i=1;i<=n;i++)cout<<par(i)<<" ";
				//~ cout<<endl;
				vector<int> ral, rvis;
				for(int i=ind-1;i>=l;i--){
					
					if(t[i]==1 ){
						//~ if(ind == 5) printf("adding edge index %lld, x[i] is %lld , whendone is %lld\n", i,x[i], whendone[x[i]]); 

						if (y[i] >= cw and whendone[x[i]] != ind){
							int px=par(u[x[i]]), py=par(v[x[i]]);
							al[px].pb(py);
							al[py].pb(px);
							ral.pb(px);
							ral.pb(py);
						}
						whendone[x[i]]=ind;

					}
					
				}
				for(int i=ind+1;i<r;i++){
					if(t[i]==1 and w[x[i]] >= cw and whendone[x[i]] != ind){
						whendone[x[i]]=ind;
						int px=par(u[x[i]]), py=par(v[x[i]]);
						al[px].pb(py);
						al[py].pb(px);
						ral.pb(px);
						ral.pb(py);
					}
				}				
				int ans=0;
				auto dfs = [&](auto dfs, int x) -> void{
					vis[x]=true;
					ans+=sz[x];
					rvis.pb(x);
					for(auto it:al[x]){
						if(vis[it])continue;
						dfs(dfs, it);
					}
				};
				dfs(dfs, par(x[ind]));
				for(auto it: ral){
					al[it].clear();
				}
				for(auto it: rvis){
					vis[it]=false;
				}
				res[ind]=ans;
			}
		}
		// implement the actual changes;
		for(int i=l;i<r;i++){
			if(t[i]==1){
				w[x[i]]=y[i];
			}
		}
	}
	for(int i=1;i<=q;i++){
		if(t[i]==2){
			cout<<res[i]<<"\n";
		}
	}
				
		
		
}

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