Submission #938121

#	Time	Username	Problem	Language	Result	Execution time	Memory
938121		mat_jur	Bridges (APIO19_bridges)	C++17	100 / 100	2123 ms	8976 KiB

bridges

#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

struct dynamicUF {
	vector<int> e;
	dynamicUF(int n): e(n, -1) {}
	stack<array<int, 3>> s;

	inline int get(int a) {
		while(e[a] >= 0) a = e[a];
		return a;
	}


	int unionn(int a, int b) {
		a = get(a); b = get(b);
		if(a == b) return 0;
		if(-e[a] > -e[b]) swap(a, b);
//		cerr << "ADD " << a << ' ' << b << '\n';
		s.push({a, b, e[a]});
		e[b] += e[a];
		e[a] = b;
		return 1;
	}

	void roll_back(int m = 1) {
		while (m--) {
			auto [a, b, sz] = s.top();
			s.pop();
//			cerr << "UNDO " << a << ' ' << b << '\n';
			e[b] -= sz;
			e[a] = sz;
		}
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<int> w(m), u(m), v(m);
	for(int i = 0; i < m; ++i) {
		cin >> u[i] >> v[i] >> w[i];
		u[i]--; v[i]--;
	}

	int q;
	cin >> q;

	vector<int> ans(q, -1);
	const int B = 600;
//	const int B = 1;
	vector<array<int, 4>> ev;
	vector<bool> changed(m);
	vector<array<int, 3>> upd;

	auto clean = [&] {
		dynamicUF sp(n);
		for(int i = 0; i < m; ++i) {
			if(!changed[i]) {ev.eb((array<int, 4>){w[i], u[i], v[i], 0});}
			else changed[i] = false;
		}
		sort(all(ev), [&](array<int, 4> x, array<int, 4> y) {
			if (x[0] != y[0]) return x[0] > y[0];
			return x[3] < y[3];
		});
		vector<int> M(m, -1);

		for(auto [d, a, b, c] : ev) {
			if(c == 0) {
				sp.unionn(a, b);
			}	
			else {
				vector<int> to_add;
				for(auto [idx, r, t] : upd) {
					if(M[idx] == -1) to_add.eb(idx);
					if(t <= b) {
						M[idx] = r;
					}
					else if(M[idx] == -1) M[idx] = w[idx];
				}
				
				int cnt = 0;
				for(auto idx : to_add) {
					int r = M[idx];
					if(r >= d) cnt += sp.unionn(u[idx], v[idx]);
					M[idx] = -1;
				}

				ans[b] = -sp.e[sp.get(a)];
				sp.roll_back(cnt);
			}
		}

		for(auto [idx, r, t] : upd) {
			w[idx] = r;
		}
		upd.clear();
		ev.clear();
	};

	for(int t = 0; t < q; ++t) {
		int c;
		cin >> c;
		if(c == 1) {
			int b, r;
			cin >> b >> r;
			b--;
			changed[b] = true;
			upd.eb((array<int, 3>){b, r, t});
		}
		else {
			int d, s;
			cin >> s >> d;
			s--;
			ev.eb((array<int, 4>){d, s, t, 1});
		}
		if(t%B == B-1) {
			clean();
		}
	}
	clean();

	for(int i = 0; i < q; i++) if(ans[i] > -1) cout << ans[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