Submission #949356

#	Time	Username	Problem	Language	Result	Execution time	Memory
949356		IBory	Bridges (APIO19_bridges)	C++17	100 / 100	1606 ms	13176 KiB

bridges

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 100007, BUCKET = 1000;
int R[MAX], Z[MAX], L[MAX], ans[MAX], sq;
pii E[MAX];
stack<pii> ST;
vector<pii> upd[MAX];

int Find(int n) {
	if (n == R[n]) return n;
	return Find(R[n]);
}

void Union(int a, int b, bool save = 0) {
	a = Find(a), b = Find(b);
	if (a == b) return;
	if (Z[a] < Z[b]) swap(a, b);
	Z[a] += Z[b];
	R[b] = a;
	if (save) ST.emplace(a, b);
}

void Rollback() {
	while (!ST.empty()) {
		auto [a, b] = ST.top(); ST.pop();
		Z[a] -= Z[b];
		R[b] = b;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, Q;
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) cin >> E[i].first >> E[i].second >> L[i];
	cin >> Q;
	vector<pair<int, pii>> Q1, Q2;

	for (int q = 0; q < Q; ++q) {
		int a, b, c;
		cin >> a >> b >> c;
		(a == 1 ? Q1 : Q2).emplace_back(q, pii{ b, c });
		if (q % BUCKET == (BUCKET - 1) || q == Q - 1) {
			iota(R, R + 50005, 0);
			fill(Z, Z + 50005, 1);
			vector<int> replaced;
			for (auto& [n, p] : Q1) {
				// Query Num, next L
				upd[p.first].emplace_back(n, p.second);
				replaced.push_back(p.first);
			}

			sort(replaced.begin(), replaced.end());
			replaced.erase(unique(replaced.begin(), replaced.end()), replaced.end());

			vector<pair<int, pii>> QS;
			for (int i = 1; i <= M; ++i) {
				if (upd[i].empty()) QS.emplace_back(L[i], E[i]);
			}
			for (auto& [n, p] : Q2) QS.emplace_back(p.second, pii{ -p.first, n });
			sort(QS.begin(), QS.end(), greater<pair<int, pii>>());

			for (auto& [n, p] : QS) {
				auto [a, b] = p;
				// Query 2: -Start, Query Num
				if (a < 0) {
					for (int& e : replaced) {
						auto it = lower_bound(upd[e].begin(), upd[e].end(), pii {b, 0});
						if (it == upd[e].begin()) {
							if (n <= L[e]) Union(E[e].first, E[e].second, 1);
						}
						else {
							if (n <= (*--it).second) Union(E[e].first, E[e].second, 1);
						}
					}
					ans[b] = Z[Find(-a)];
					Rollback();
				}
				else Union(a, b);
			}

			for (auto& [n, p] : Q1) {
				upd[p.first].clear();
				L[p.first] = p.second;
			}
			Q1.clear(); Q2.clear();
		}
	}

	for (int q = 0; q < Q; ++q) if (ans[q]) cout << ans[q] << '\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