Submission #198057

#	Time	Username	Problem	Language	Result	Execution time	Memory
198057		QCFium	Bridges (APIO19_bridges)	C++14	100 / 100	1892 ms	11696 KiB

bridges

#include <bits/stdc++.h>
 
#ifdef _WIN32
#	define getchar_fast _getchar_nolock
#else
#	define getchar_fast getchar_unlocked
#endif
int ri() {
	int r = 0, c, s = 0;
	for (;;) {
		c = getchar_fast();
		if (c == '-') {
			s = 1;
			break;
		}
		if (c <= '9' && c >= '0') {
			r = c - '0';
			break;
		}
	}
	for (;;) {
		c = getchar_fast();
		if (c < '0' || c > '9') break;
		r = r * 10 + c - '0';
	}
	if (s) r = -r;
	return r;
}
struct UnionFind {
	std::vector<int> data;
	std::vector<int> size;
	std::vector<std::vector<std::pair<int, int> > > hens;
	UnionFind (int n) : data(n, -1), size(n, 0), hens(n) {}
	void add_hen(int start, int end, int index) { hens[start].push_back({index, end}); }
	int root(int i) { return data[i] < 0 ? i : data[i] = root(data[i]); }
	bool unite(int i, int j) {
		i = root(i);
		j = root(j);
		if (i == j) return false;
		if (-data[i] + size[i] > -data[j] + size[j]) std::swap(i, j);
		// i->j
		hens[j].reserve(hens[j].size() + hens[i].size());
		for (auto k : hens[i]) hens[j].push_back(k);
		hens[i].clear();
		size[j] += size[i];
		data[j] += data[i];
		data[i] = j;
		return true;
	}
	int get_size(int i) { return -data[root(i)]; }
	void clear() {
		std::fill(data.begin(), data.end(), -1);
		std::fill(size.begin(), size.end(), 0);
		for (auto &i : hens) i.clear();
	}
};
 
int main() {
	int n = ri(), m = ri();
	struct Hen {
		int a;
		int b;
		int cost;
		int id;
	};
	std::vector<Hen> hens(m);
	for (int i = 0; i < m; i++) hens[i].a = ri() - 1, hens[i].b = ri() - 1, hens[i].cost = ri(), hens[i].id = i;
	
	struct Query {
		int type;
		int index;
		int cost;
		int id;
	};
	int q = ri();
	std::vector<Query> qs(q);
	for (int i = 0; i < q; i++) qs[i].type = ri() - 1, qs[i].index = ri() - 1, qs[i].cost = ri(), qs[i].id = i;
#define BLOCK 1000
	std::vector<bool> changing(m);
	std::vector<int> cost(m);
	for (int i = 0; i < m; i++) cost[i] = hens[i].cost;
	std::vector<bool> used(n);
	std::vector<int> used_rollback;
	std::vector<int> res(q);
	for (int i = 0; i < q; i += BLOCK) {
		auto hens_copy = hens;
		std::sort(hens_copy.begin(), hens_copy.end(), [] (auto &i, auto &j) { return i.cost > j.cost; });
		std::vector<Query> query, change;
		for (int j = i; j < q && j < i + BLOCK; j++) {
			if (!qs[j].type) changing[qs[j].index] = true, change.push_back(qs[j]);
			else query.push_back(qs[j]);
		}
		std::sort(query.begin(), query.end(), [] (auto &i, auto &j) { return i.cost > j.cost; });
		static UnionFind uni(n);
		uni.clear();
		for (int j = 0; j < m; j++) if (changing[j]) uni.add_hen(hens[j].a, hens[j].b, j), uni.add_hen(hens[j].b, hens[j].a, j);
		int head = 0;
		for (auto j : query) {
			static std::vector<std::pair<int, int> > rollback;
			for (auto &k : change) {
				if (k.id > j.id) break;
				rollback.push_back({k.index, cost[k.index]}), cost[k.index] = k.cost;
			}
			while (head < m && hens_copy[head].cost >= j.cost) {
				if (!changing[hens_copy[head].id]) uni.unite(hens_copy[head].a, hens_copy[head].b);
				head++;
			}
			auto use = [&] (int i) { used_rollback.push_back(i); used[i] = true; return i; };
			std::queue<int> que;
			que.push(use(uni.root(j.index)));
			int cur = 0;
			while (que.size()) {
				int k = que.front();
				que.pop();
				cur += -uni.data[k];
				for (auto l : uni.hens[k]) {
					if (cost[l.first] < j.cost) continue;
					int target = uni.root(l.second);
					if (!used[target]) {
						use(target);
						que.push(target);
					}
				}
			}
			res[j.id] = cur;
			for (auto k : used_rollback) used[k] = false;
			used_rollback.clear();
			for (; rollback.size(); rollback.pop_back()) cost[rollback.back().first] = rollback.back().second;
		}
		
		for (int j = i; j < q && j < i + BLOCK; j++) {
			if (!qs[j].type) {
				cost[qs[j].index] = qs[j].cost;
				hens[qs[j].index].cost = qs[j].cost;
				changing[qs[j].index] = false;
			}
		}
	}
	for (int i = 0; i < q; i++) if (qs[i].type) printf("%d\n", res[i]);
	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