Submission #951191

#	Time	Username	Problem	Language	Result	Execution time	Memory
951191		MinaRagy06	Bridges (APIO19_bridges)	C++17	27 / 100	766 ms	225060 KiB

bridges

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

const int N = 100'005, B = 200;
int par[N], sz[N], par2[N], sz2[N];
int find(int u) {
	if (u == par[u]) {
		return u;
	}
	return par[u] = find(par[u]);
}
void join(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (sz[u] < sz[v]) swap(u, v);
	par[v] = u;
	sz[u] += sz[v];
}
vector<int> in;
void add(int u) {
	in.push_back(u);
	par2[u] = par[u];
	sz2[u] = sz[u];
}
int find2(int u) {
	if (par2[u] == -1) {
		add(u);
	}
	if (par2[u] == u) {
		return u;
	}
	return par2[u] = find2(par2[u]);
}
void join2(int u, int v) {
	u = find2(u), v = find2(v);
	if (u == v) return;
	if (sz2[u] < sz2[v]) swap(u, v);
	par2[v] = u;
	sz2[u] += sz2[v];
}
array<int, 3> qq[N];
array<int, 3> e[N];
int w[N], ans[N];
vector<array<int, 3>> vals[N];
vector<array<int, 3>> ask[N];
set<int> gud[2 * N];
bool bad[N];
vector<int> vs;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> e[i][1] >> e[i][2] >> e[i][0];
		vs.push_back(e[i][0]);
	}
	bad[m] = 1;
	int q;
	cin >> q;
	for (int k = 0; k < q; k++) {
		cin >> qq[k][0] >> qq[k][1] >> qq[k][2];
		if (qq[k][0] == 1) {
			qq[k][1]--;
			vs.push_back(qq[k][2]);
		}
	}
	sort(vs.begin(), vs.end());
	vs.resize(unique(vs.begin(), vs.end()) - vs.begin());
	for (int i = 0; i < m; i++) {
		e[i][0] = lower_bound(vs.begin(), vs.end(), e[i][0]) - vs.begin();
		w[i] = e[i][0];
		gud[e[i][0]].insert(i);
	}
	for (int k = 0; k < q; k++) {
		if (qq[k][0] == 1) {
			qq[k][2] = lower_bound(vs.begin(), vs.end(), qq[k][2]) - vs.begin();
		} else {
			qq[k][2] = lower_bound(vs.begin(), vs.end(), qq[k][2]) - vs.begin();
		}
	}
// 	for (int i = 0; i < m; i++) {
// 		cout << e[i][1] << ' ' << e[i][2] << ' ' << e[i][0] << '\n';
// 	}
// 	cout << q << '\n';
// 	for (int k = 0; k < q; k++) {
// 		cout << qq[k][0] << ' ' << qq[k][1] << ' ' << qq[k][2] << '\n';
// 	}
	memset(ans, -1, sizeof ans);
	vector<int> v;
	int prv = 0;
	auto process = [&] (int L, int R) {
		for (int k = L; k <= R; k++) {
			int t = qq[k][0];
			if (t == 1) {
				int b = qq[k][1], r = qq[k][2];
				w[b] = r;
			} else {
				int x = qq[k][1], mx = qq[k][2];
				ask[mx].push_back({x, mx, k});
				for (auto i : v) {
					if (w[i] >= mx) {
						vals[k].push_back({e[i][1], e[i][2], w[i]});
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			par[i] = i;
			sz[i] = 1;
			par2[i] = sz2[i] = -1;
		}
		for (int i = vs.size() - 1; i >= 0; i--) {
			for (auto idx : gud[i]) {
				if (!bad[idx]) {
					join(e[idx][1], e[idx][2]);
				}
			}
			for (auto [x, y, idx] : ask[i]) {
				for (auto [U, V, c] : vals[idx]) {
					join2(U, V);
				}
				ans[idx] = sz2[find2(x)];
				for (auto j : in) {
					par2[j] = sz2[j] = -1;
				}
				in.clear();
			}
			ask[i].clear();
		}
		for (int k = L; k <= R; k++) {
			vals[k].clear();
			int t = qq[k][0];
			if (t == 1) {
				int b = qq[k][1], r = qq[k][2];
				gud[e[b][0]].erase(b);
				e[b][0] = r;
				gud[e[b][0]].insert(b);
			}
		}
	};
	for (int k = 0; k < q; k++) {
		if (v.size() == B) {
			process(prv, k - 1);
			for (auto i : v) {
				bad[i] = 0;
			}
			v.clear();
			prv = k;
		}
		int t = qq[k][0];
		if (t == 1) {
			int b = qq[k][1];
			if (!bad[b]) {
				bad[b] = 1;
				v.push_back(b);
			}
		} else {
			ans[k] = 1;
		}
	}
	process(prv, q - 1);
	for (auto i : ans) {
		if (i == -1) continue;
		cout << i << '\n';
	}
	return 0;
}

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