Submission #444298

#	Time	Username	Problem	Language	Result	Execution time	Memory
444298		dutch	Bridges (APIO19_bridges)	C++17	100 / 100	2050 ms	9840 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define F(z) while(e[z] >= 0) z = e[z];

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

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

void unite(int i, bool c){
	int u = g[0][i], v = g[1][i];
	F(u) F(v)
	if(u == v) return;
	if(e[u] > e[v]) swap(u, v);
	if(c){
		rb[0][p] = u, rb[1][p] = v;
		rb[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];
		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){
				on[b[1][i]] = 1;
				curr.push_back(b[1][i]);
			}
		}

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

				F(b[1][i[2]])
				b[3][i[2]] = -e[b[1][i[2]]];

				for(int j=l; j<r; ++j){
					if(b[0][j] < 2) on[b[1][j]] = 1;
					if(p) --p, e[rb[0][p]] -= (e[rb[1][p]] = rb[2][p]);
				}	
			}
		}

		for(int i=l; i<r; ++i){
			if(b[0][i] < 2){
				on[b[1][i]] = 0;
				w[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