Submission #938072

#	Time	Username	Problem	Language	Result	Execution time	Memory
938072		mat_jur	Bridges (APIO19_bridges)	C++17	14 / 100	2680 ms	7616 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);
		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();
			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);
	vector<int> C(q);

	auto clean = [&](int L, int R) {
		for(int i = L; i <= R; i++) 
			if(C[i] == 1) changed[s[i]] = true;
			else ev.eb(mp(i, 1));

		dynamicUF sp(n);
		for(int i = 0; i < m; ++i) {
			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;
		});

		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;
				map<int, int> M;
				for(int t = L; t <= R; ++t) {
					if(C[t] != 1) continue;
					if(t <= b) M[s[t]] = w[1][t];
					else if(M[s[t]] == 0) M[s[t]] = w[0][s[t]];
				}
				
				int cnt = 0;
				for(auto [idx2, r] : M) {
					if(r >= d) cnt += sp.unionn(u[idx2], v[idx2]);
				}

				ans[b] = -sp.e[sp.get(a)];
				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) {
		cin >> C[t];
		cin >> s[t] >> w[1][t];
		s[t]--;
//		if(c == 1) {
//			int b, r;
//			cin >> b >> r;
//			b--;
//			changed[b] = true;
//			upd.eb((array<int, 3>){b, r, t});
//		}
//		else {
//			s[t]--;
//			ev.eb(mp(t, 1));
//		}
	}
	for(int i = 0; i < q; i += B) {
		clean(i, min(q-1, i+B-1));
	}

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

	return 0;
}

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