Submission #1045180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045180		vjudge1	Bridges (APIO19_bridges)	C++17	59 / 100	3013 ms	13708 KiB

bridges

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
	#include "debug.h"
#else 
	#define debug(...) void(23)
#endif

constexpr int maxN = int(1E5) + 5;
constexpr int SQRT = 317;

struct DSU {
	std::vector<int> par, siz;
	std::vector<std::pair<int&, int>> history;
	DSU() : DSU(0) {}
	DSU(int n) { init(n); }
	void init(int n) {
		par.assign(n, 0);
		siz.assign(n, 1);
		std::iota(par.begin(), par.end(), 0);
	}
	int get(int x) {
		while(x != par[x]) {
			x = par[x];
		}
		return x;
	}
	bool unite(int a, int b) {
		a = get(a), b = get(b);
		if(a == b) {
			return false;
		} else if(siz[a] > siz[b]) {
			std::swap(a, b);
		}
		history.emplace_back(par[a], a);
		history.emplace_back(siz[b], siz[b]);
		par[a] = b;
		siz[b] += siz[a];
		return true;
	}
	int size(int x) {
		return siz[get(x)];
	}
	void roll() {
		history.back().first = history.back().second;
		history.pop_back();
		history.back().first = history.back().second;
		history.pop_back();
	}
	int snap() {
		return history.size();
	}
};

std::vector<int> g[maxN];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N, M;
	std::cin >> N >> M;
	std::vector<int> A(M), B(M), C(M), idx(M);
	for(int i = 0; i < M; ++i) {
		std::cin >> A[i] >> B[i] >> C[i];
		--A[i], --B[i];
	}
	int Q;
	std::cin >> Q;
	std::vector<int> T(Q), X(Q), Y(Q);
	for(int i = 0; i < Q; ++i) {
		std::cin >> T[i] >> X[i] >> Y[i];
		if(T[i] == 1) {
			--X[i];
		} else {
			--X[i];
		}
	}

	debug("wtf");

	std::vector<int> ans(Q, -1);
	std::vector<bool> changed(M);
	for(int l = 0; l < Q; l += SQRT) {
		int r = std::min(Q, l + SQRT);
		std::vector<int> qq;
		for(int i = l; i < r; ++i) {
			if(T[i] == 1) {
				changed[X[i]] = true;
				g[X[i]].emplace_back(i);
			} else {
				qq.emplace_back(i);
			}
		}
		std::vector<int> nope, yep;
		for(int i = 0; i < M; ++i) {
			if(!changed[i]) {
				nope.emplace_back(i);
			} else {
				yep.emplace_back(i);
			}
		}

		std::sort(qq.begin(), qq.end(), [&](int lhs, int rhs) {
			return Y[lhs] > Y[rhs];
		});
		std::sort(nope.begin(), nope.end(), [&](int lhs, int rhs) {
			return C[lhs] > C[rhs];
		});

		debug(nope, yep);

		DSU dsu(N);
		int ptr = 0;
		for(int i : qq) {
			debug(i, X[i], Y[i]);
			while(ptr < int(nope.size()) && C[nope[ptr]] >= Y[i]) {
				debug(nope[ptr], A[nope[ptr]], B[nope[ptr]]);
				dsu.unite(A[nope[ptr]], B[nope[ptr]]);
				++ptr;
			}
			int s = dsu.snap();
			for(int j : yep) {
				debug(j);
				auto it = std::upper_bound(g[j].begin(), g[j].end(), i);
				int cost;
				if(it == g[j].begin()) {
					cost = C[j];
				} else {
					--it;
					cost = Y[*it];
				}
				debug(cost, A[j], B[j]);
				if(cost >= Y[i]) {
					debug("united");
					dsu.unite(A[j], B[j]);
				}
				debug("finished");
			}
			#ifdef DEBUG
				for(int k = 0; k < N; ++k) {
					debug(dsu.get(k), dsu.size(k));
				}
			#endif
			ans[i] = dsu.size(X[i]);
			while(dsu.snap() != s) {
				dsu.roll();
			}
			debug("yey\n\n");
		}

		debug("bruh");
		for(int i = l; i < r; ++i) {
			if(T[i] == 1) {
				g[X[i]].pop_back();
				changed[X[i]] = false;
				C[X[i]] = Y[i];
			} 
		}
		debug("wtf");
	}

	for(int i = 0; i < Q; ++i) {
		if(ans[i] != -1) {
			std::cout << ans[i] << '\n';
		}
	}

	return 0;
}

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