Submission #951183

#	Time	Username	Problem	Language	Result	Execution time	Memory
951183		MinaRagy06	Bridges (APIO19_bridges)	C++17	27 / 100	606 ms	524288 KiB

bridges

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

const int N = 100'005, B = 100'005;
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, 4> e[N];
int w[N], ans[N], pos[N];
vector<array<int, 3>> vals[N];
vector<array<int, 3>> ask[N];
bool bad[N];
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];
		e[i][3] = i;
	}
	bad[m] = 1;
	sort(e, e + m);
	for (int i = 0; i < m; i++) {
		w[i] = e[i][0];
		pos[e[i][3]] = i;
	}
	int q;
	cin >> q;
	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;
// 				cout << ", " << b << ' ' << r << '\n';
			} else {
				int x = qq[k][1], mx = qq[k][2];
				int idx = lower_bound(e, e + m, (array<int, 4>) {mx, 0, 0, 0}) - e;
				ask[idx].push_back({x, mx, k});
				for (auto i : v) {
// 					cout << ">>> " << i << ' ' << w[i] << '\n';
					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 = m; i >= 0; i--) {
			if (!bad[i]) {
// 				cout << "> " << e[i][1] << ' ' << e[i][2] << " (" << e[i][0] << ")" << '\n';
				join(e[i][1], e[i][2]);
			}
			for (auto [x, y, idx] : ask[i]) {
				for (auto [U, V, c] : vals[idx]) {
// 					if (idx == 1) {
// 						cout << ">> " << U << ' ' << V << ' ' << c << '\n';
// 					}
					if (c >= y) {
						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();
		}
		for (int i = 0; i < m; i++) {
			e[i][0] = w[i];
		}
		sort(e, e + m);
		for (int i = 0; i < m; i++) {
			w[i] = e[i][0];
			pos[e[i][3]] = i;
		}
	};
	for (int k = 0; k < q; k++) {
		ans[k] = -1;
		if (v.size() == B) {
			process(prv, k - 1);
			for (auto i : v) {
				bad[i] = 0;
			}
			v.clear();
			prv = k;
		}
		cin >> qq[k][0] >> qq[k][1] >> qq[k][2];
		int t = qq[k][0];
		if (t == 1) {
			qq[k][1]--;
			qq[k][1] = pos[qq[k][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