Submission #1126856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126856		Mikael639	Bridges (APIO19_bridges)	C++20	100 / 100	1732 ms	125912 KiB

bridges

#include <bits/stdc++.h>

#define fi first
#define se second

#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define ForD(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
#define coutE(x) {cout << x << '\n'; return;}
#define pb push_back
#define pf push_front

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define bs binary_search
#define ub upper_bound
#define lb lower_bound

#define endl '\n'

#define db long double
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>

using namespace std;

const int N = 1e5 + 5;
const int B = 1000;

int n, m, q;

struct edge{
	int u, v, w;
} ed[N];

struct query{
	int t, x, w;
} quer[N];

bool bad[N];
int ans[N];
vi g[N];

int par[50005];
stack<pair<int&, int>> history;

int find(int u){
	while (par[u] > 0) u = par[u];
	return u;
}

void rollBack(int t){
	while (sz(history) > t){
		history.top().fi = history.top().se;
		history.pop();
	}
}

void Union(edge e){
	int u = find(e.u), v = find(e.v);
	if (u == v) return;
	if (par[u] > par[v]) swap(u, v);
	
	history.push({par[u], par[u]});
	history.push({par[v], par[v]});
	
	par[u] += par[v];
	par[v] = u;
}

signed main(){

	ios_base::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	For(i, 1, m){
		cin >> ed[i].u >> ed[i].v >> ed[i].w;
	}
	
	cin >> q;
	For(i, 1, q){
		cin >> quer[i].t >> quer[i].x >> quer[i].w;
	}
	
	for (int l = 1; l <= q; l += B){
		memset(par, -1, sizeof par);
		while (!history.empty()) history.pop();
		
		int r = min(q, l + B - 1);
		
		vi ask, changed, unchanged;
		For(i, l, r){
			if (quer[i].t == 1){
				//change is bad
				bad[quer[i].x] = 1; 
				//remember that edge's id not query's id
			}
			else{
				ask.pb(i);
			}
		}
		
		For(i, 1, m){
			if (bad[i])
				changed.pb(i);
			else
				unchanged.pb(i);
			
			//remember to reset
			bad[i] = 0;
		}
		
		//O(B^2)
		For(i, l, r){
			if (quer[i].t == 1){
				//update new weight
				ed[quer[i].x].w = quer[i].w;
			}
			else{
				for (int j: changed){
					if (ed[j].w >= quer[i].w){
						//g[i] saves bad edges that i needs
						g[i].pb(j);
					}
				}
			}
		}
		
		sort(all(ask), [&](int i, int j){
			return quer[i].w > quer[j].w;
		});
		
		sort(all(unchanged), [&](int i, int j){
			return ed[i].w > ed[j].w;
		});
		
		int pnt = 0;
		
		//O(B * (m + B))
		for (int i: ask){
			while (pnt < sz(unchanged) && ed[unchanged[pnt]].w >= quer[i].w)
				Union(ed[unchanged[pnt++]]);
			
			int last = sz(history);
			for (int j: g[i]) Union(ed[j]);
			
			ans[i] = -par[find(quer[i].x)];
			
			rollBack(last); //O(B)
			
			//reset
			g[i].clear();
		}
	}
	
	For(i, 1, q) if (quer[i].t == 2)
		cout << ans[i] << endl;

	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