Submission #742587

#	Time	Username	Problem	Language	Result	Execution time	Memory
742587		RushB	Bridges (APIO19_bridges)	C++17	100 / 100	2265 ms	106656 KiB

bridges

#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
using namespace std;
const long long INF = 1ll << 60;
const int N = 1e5 + 5;

int dpr[N];
vector<array<int, 3>> undo;
int gpr(int x) { 
	while (dpr[x] >= 0) x = dpr[x];
	return x;
}
bool merge(int u, int v) {
	u = gpr(u), v = gpr(v);
	if (u == v) return false;
	if (dpr[u] < dpr[v]) swap(u, v); //v is bigger now
	undo.push_back({u, v, dpr[u]});
	dpr[v] += dpr[u];
	dpr[u] = v;
	return true;
}
void rollback() {
	const auto &a = undo.back();
	dpr[a[0]] = a[2];
	dpr[a[1]] -= a[2];
	undo.pop_back();
}

const int SQ = 1000;
const int SQ2 = N / SQ + 5;
int a[N], b[N], U[N], W[N], V[N], n, m, q, ans[N];
short t[N];

void solve() {
	//t = 1 CHANGE
	//t = 2 SOAL
	FOR(i, 0, SQ2) {
		int L = i * SQ, R = min(q, (i + 1) * SQ);
		if (L >= q) break;

		memset(dpr, -1, sizeof dpr);

		bitset<N> change = 0, mark = 0;
		vector<int> Q, E, NE;

		FOR(j, L, R) {
			if (t[j] == 1) change[a[j]] = true;
			else Q.push_back(j);
		}
		FOR(j, 0, m) (change[j] ? NE : E).push_back(j);

		sort(E.rbegin(), E.rend(), [&](const int x, const int y) {return W[x] < W[y];});
		sort(Q.begin(), Q.end(), [&](const int x, const int y) {return b[x] < b[y];});

		for (auto qid: Q) {
			while (E.size() && W[E.back()] <= b[qid]) {
				merge(U[E.back()], V[E.back()]);
				E.pop_back();
			}
			int cnt = 0;
			for (int j = qid; j >= L; j--) if (t[j] == 1 && !mark[a[j]]) {
				if (b[j] <= b[qid]) {
					cnt += merge(U[a[j]], V[a[j]]);
					mark[a[j]] = true;
				}
				mark[a[j]] = true;
			}
			for (auto e: NE) if (!mark[e]) {
				mark[e] = true;
				if (W[e] <= b[qid]) {
					cnt += merge(U[e], V[e]);
					mark[e] = true;
				}
			}
			ans[qid] = dpr[gpr(a[qid])];

			while (cnt--) rollback();

			FOR(j, L, qid) mark[a[j]] = false;
			for (auto e: NE) mark[e] = false;
		}
		FOR(j, L, R) if (t[j] == 1) W[a[j]] = b[j];
	}
	FOR(i, 0, q) if (t[i] == 2) cout << -ans[i] << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	FOR(i, 0, m) {
		cin >> U[i] >> V[i] >> W[i];
		U[i]--, V[i]--;
		W[i] = -W[i];
	}
	cin >> q;
	FOR(i, 0, q) {
		cin >> t[i] >> a[i] >> b[i];
		a[i]--;
		b[i] = -b[i];
	}
	solve();

	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