Submission #938046

#	Time	Username	Problem	Language	Result	Execution time	Memory
938046		mat_jur	Bridges (APIO19_bridges)	C++17	73 / 100	3025 ms	8504 KiB

bridges

#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;

	int get(int a) {return e[a] < 0 ? a : get(e[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[2], u(m), v(m);
	w[0] = vector(m, 0);
	for(int i = 0; i < m; ++i) {
		cin >> u[i] >> v[i] >> w[0][i];
		u[i]--; v[i]--;
	}

	int q;
	cin >> q;

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

	auto clean = [&] {
//		cerr << "CLEAN \n";
//		debug(upd);
//		debug(changed);
//		debug(ev);
//		debug(w[0]);
//		debug(w[1]);
//		debug(s);

		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;
			if(!changed[i]) ev.eb(mp(i, 0));
			else changed[i] = false;
		}
		sort(all(ev), [&](pair<int, int> x, pair<int, int> y) {
			if (w[x.se][x.fi] != w[y.se][y.fi]) return w[x.se][x.fi] > w[y.se][y.fi];
			return x.se < y.se;
		});
		debug(ev);

		for(auto [idx, c] : ev) {
			if(c == 0) {
				sp.unionn(u[idx], v[idx]);
			}	
			else {
				int d = w[1][idx], a = s[idx], b = idx;
//				cerr << "QUERY " << b << ' ' << mp(a, d) << '\n';
				debug(sp.e);
				map<int, int> M;
				for(auto [idx2, r, t] : upd) {
					if(t <= b) M[idx2] = r;
					else if(M[idx2] == 0) M[idx2] = w[0][idx2];
				}
				
				int cnt = 0;
				for(auto [idx2, r] : M) {
					if(r >= d) cnt += sp.unionn(u[idx2], v[idx2]);
				}

//				cerr << "ANS \n";
//				debug(cnt);
//				debug(sp.e);
				ans[b] = -sp.e[sp.get(a)];
//				cerr << "ROLL_BACK \n";
				sp.roll_back(cnt);
			}
		}

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

	w[1] = vector(q, 0);
	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 {
			cin >> s[t] >> w[1][t];
			s[t]--;
			ev.eb(mp(t, 1));
		}
		if(t%B == B-1) {
			clean();
		}
	}
	clean();

	debug(ans);
	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: 0 / 27