Submission #951944

#	Time	Username	Problem	Language	Result	Execution time	Memory
951944		MinaRagy06	Bridges (APIO19_bridges)	C++17	100 / 100	1040 ms	127220 KiB

bridges

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

const int N = 100'005, B = 700;
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;
array<int, 3> qq[N];
array<int, 3> e[N];
int w[N], ans[N];
vector<int> vals[N];
vector<array<int, 2>> ask[N];
set<int> gud[N];
bool bad[N];
vector<int> vs;
bool vis[N];
vector<int> adj[N];
void dfs(int i, int &cnt) {
	cnt += sz[i];
	in.push_back(i);
	vis[i] = 1;
	for (auto nxt : adj[i]) {
		if (!vis[nxt]) {
			dfs(nxt, cnt);
		}
	}
}
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];
	}
	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]--;
		} else {
			vs.push_back(qq[k][2]);
		}
	}
	vs.push_back(0);
	vs.push_back(1e9 + 1);
	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] + 1) - vs.begin() - 1;
		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] + 1) - vs.begin() - 1;
		} else {
			qq[k][2] = lower_bound(vs.begin(), vs.end(), qq[k][2]) - vs.begin();
		}
	}
	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, k});
				for (auto i : v) {
					if (w[i] >= mx) {
						vals[k].push_back(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, eidx] : ask[i]) {
				for (auto idx : vals[eidx]) {
					if (find(e[idx][1]) != find(e[idx][2])) {
						adj[find(e[idx][1])].push_back(find(e[idx][2]));
						adj[find(e[idx][2])].push_back(find(e[idx][1]));
					}
				}
				int cnt = 0;
				dfs(find(x), cnt);
				ans[eidx] = cnt;
				for (auto j : in) {
					vis[j] = 0;
				}
				in.clear();
				for (auto idx : vals[eidx]) {
					if (find(e[idx][1]) != find(e[idx][2])) {
						adj[find(e[idx][1])].pop_back();
						adj[find(e[idx][2])].pop_back();
					}
				}
			}
			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 (k - prv == 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: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27