Submission #444288

#	Time	Username	Problem	Language	Result	Execution time	Memory
444288		dutch	Bridges (APIO19_bridges)	C++17	100 / 100	2508 ms	16040 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 5e4, LIM = 1e5, SQRT = 500;

int n, m, q, e[MAXN], w[LIM], wCurr[LIM], rollback[3][SQRT], p, g[2][LIM], b[4][LIM];
bool active[LIM];

int find(int u){
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

void unite(int i){
	int u = find(g[0][i]), v = find(g[1][i]);
	if(u == v) return;

	if(e[u] > e[v]) swap(u, v);
	e[u] += e[v], e[v] = u;
}

void uniteWithRollback(int i){
	int u = g[0][i], v = g[1][i];
	while(e[u] >= 0) u = e[u];
	while(e[v] >= 0) v = e[v];
	if(u == v) return;

	if(e[u] > e[v]) swap(u, v);

	rollback[0][p] = u, rollback[1][p] = v;
	rollback[2][p++] = e[v];

	e[u] += e[v], e[v] = u;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;

	vector<array<int, 3>> a(m); // -wt, type, time/queryID
	for(int i=0; i<m; ++i){
		cin >> g[0][i] >> g[1][i] >> w[i];
		--g[0][i], --g[1][i];
		wCurr[i] = w[i];
		a[i] = {-w[i], 1, -1-i};
	}
	cin >> q;
	a.resize(m+q);
	for(int i=0; i<q; ++i){
		cin >> b[0][i] >> b[1][i] >> b[2][i];
		--b[1][i];
		a[i+m] = {-b[2][i], b[0][i], i};
	}

	sort(a.begin(), a.end());

	for(int l=0; l<q; l+=SQRT){
		int r = min(q, l+SQRT);
		vector<int> curr;
		for(int i=l; i<r; ++i){
			if(b[0][i] == 1){
				active[b[1][i]] = 1;
				curr.push_back(b[1][i]);
			}
		}

		fill(e, e+n, -1);
		for(auto &i : a){
			if(i[1] < 2){
				if(i[2] < 0){
					int j = -i[2]-1;
					if(!active[j] && -i[0] == w[j]) unite(j);
				}else if(i[2] < l){
					int j = b[1][i[2]];
					if(!active[j] && -i[0] == w[j]) unite(j);
				}
			}else if(l <= i[2] && i[2] < r){
				for(int j=l; j<i[2]; ++j){
					if(b[0][j] < 2) wCurr[b[1][j]] = b[2][j];
				}
				
				for(int &j : curr) if(wCurr[j] >= -i[0]) uniteWithRollback(j);

				int u = b[1][i[2]];
				while(e[u] >= 0) u = e[u];
				// assert(e[u] < 0);
				b[3][i[2]] = -e[u];

				while(p){
					--p;
					e[rollback[0][p]] -= (e[rollback[1][p]] = rollback[2][p]);
				}

				for(int j=l; j<i[2]; ++j){
					if(b[0][j] < 2) wCurr[b[1][j]] = w[b[1][j]];
				}	
			}
		}

		for(int i=l; i<r; ++i){
			if(b[0][i] != 	1) continue;
			active[b[1][i]] = 0;
			w[b[1][i]] = wCurr[b[1][i]] = b[2][i];
		}
	}

	for(int i=0; i<q; ++i) if(b[0][i] > 1) cout << b[3][i] << '\n';
}

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