Submission #198023

#	Time	Username	Problem	Language	Result	Execution time	Memory
198023		QCFium	Bridges (APIO19_bridges)	C++14	100 / 100	2386 ms	11884 KiB

bridges

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
int64_t rs64() {
	long long n;
	scanf("%lld", &n);
	return n;
}

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
		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)]; }
};

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 800
	std::vector<bool> changing(m);
	std::vector<int> cost(m);
	std::vector<int> h_start(m), h_end(m);
	for (int i = 0; i < m; i++) cost[hens[i].id] = hens[i].cost, h_start[hens[i].id] = hens[i].a, h_end[hens[i].id] = hens[i].b;
	std::vector<int> ch_rollback;
	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> local;
		for (int j = i; j < q && j < i + BLOCK; j++) {
			local.push_back(qs[j]);
			if (!qs[j].type) ch_rollback.push_back(qs[j].index), changing[qs[j].index] = true;
		}
		std::sort(local.begin(), local.end(), [] (auto &i, auto &j) { return i.cost > j.cost; });
		UnionFind uni(n);
		for (int j = 0; j < m; j++) if (changing[j]) uni.add_hen(h_start[j], h_end[j], j), uni.add_hen(h_end[j], h_start[j], j);
		int head = 0;
		for (auto j : local) {
			if (!j.type) continue;
			static std::vector<std::pair<int, int> > rollback;
			for (int k = i; k < j.id; k++) if (!qs[k].type) rollback.push_back({qs[k].index, cost[qs[k].index]}), cost[qs[k].index] = qs[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;
			}
		}
		for (auto i : ch_rollback) changing[i] = false;
		ch_rollback.clear();
	}
	for (int i = 0; i < q; i++) if (qs[i].type) printf("%d\n", res[i]);
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int ri()':
bridges.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bridges.cpp: In function 'int64_t rs64()':
bridges.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~

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