Submission #520637

#	Time	Username	Problem	Language	Result	Execution time	Memory
520637		c28dnv9q3	Keys (IOI21_keys)	C++17	100 / 100	1117 ms	106632 KiB

keys

// --- algolib/union-find.h ---
// union find, optionally with tags for each component. this is useful
// for example when compressing components. enable using template parameter
#include <algorithm>
#include <type_traits>
#include <numeric>
#include <vector>


template<typename T = void, typename enable = void>
class UnionFind {
	std::vector<int> p, size_;

public:
	UnionFind(int n = 0) : p(n), size_(n, 1) {
		std::iota(p.begin(), p.end(), 0);
	}

	int create() {
		int r = p.size();
		p.push_back(r);
		size_.push_back(1);
		return r;
	}

	int find(int i) {
		if (i == p[i])
			return i;
		return p[i] = find(p[i]);
	}
	int operator[](int i) { return find(i); }
	int size(int i) { return size_[find(i)]; }

	bool connected(int a, int b) { return find(a) == find(b); }

	bool connect(int a, int b) {
		a = find(a), b = find(b);
		if (a == b)
			return false;
		if (size_[a] > size_[b])
			std::swap(a, b);
		size_[b] += size_[a];
		p[a] = b;
		return true;
	}
};

// connect(a, b) maintains tag(b)
template<typename T>
class UnionFind<T, typename std::enable_if_t<!std::is_same_v<T, void>>>
	: public UnionFind<void> {
	std::vector<T> tags;

public:
	UnionFind(int n = 0) : UnionFind<void>(n), tags(n) { }

	void create() {
		UnionFind<void>::create();
		tags.emplace_back();
	}

	bool connect(int a, int b) {
		T old = tag(b);
		bool res = UnionFind<void>::connect(a, b);
		set_tag(b, old);
		return res;
	}

	void set_tag(int i, const T& t) { tags[find(i)] = t; }
	const T& tag(int i) { return tags[find(i)]; }
};
// ----------------
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300005;

int n;
vector<int> ans;
struct Edge {
	int to, key; // key required
	bool operator<(const Edge& o) const {
		// cannot just use key, otherwise edges get lost (set)
		return tie(key, to) < tie(o.key, o.to);
	}
};
vector<int> out_can[MAX_N]; // only the to
set<Edge> out_blocked[MAX_N];
set<int> keys[MAX_N];
int par[MAX_N]; // parent in tree
UnionFind weakly(MAX_N); // weakly connected components
UnionFind<int> compressed(MAX_N);

// merge i into j, smaller to larger style
void merge(int i, int j) {
	if (compressed.size(i) > compressed.size(j)) {
		out_can[i].swap(out_can[j]);
		out_blocked[i].swap(out_blocked[j]);
		keys[i].swap(keys[j]);
	}
	compressed.connect(i, j); // tag of j is maintained
	out_can[j].insert(out_can[j].end(),
			out_can[i].begin(), out_can[i].end());
	out_can[i].clear();
	for (int key : keys[i])
		if (keys[j].insert(key).second) { // promote
			auto it = out_blocked[j].lower_bound({ -1, key });
			while (it != out_blocked[j].end() && it->key == key) {
				out_can[j].push_back(it->to);
				it = out_blocked[j].erase(it);
			}
		}
	keys[i].clear();
	for (auto& x : out_blocked[i])
		if (keys[j].find(x.key) == keys[j].end())
			out_blocked[j].insert(x);
		else if (!compressed.connected(j, x.to)) // pruning back edges
			out_can[j].push_back(x.to);
	out_blocked[i].clear();
	return;
}

void solve() {
	using pq_key = pair<int, int>; // size, vertex (roots order by size)
	priority_queue<pq_key, vector<pq_key>, greater<pq_key>> roots;
	// tags are the representatives (where keys & edges are stored)
	for (int i = 0; i < n; i++) {
		compressed.set_tag(i, i);
		roots.push({ 1, i });
	}
	// != -1 means we already found an answer of size done_size
	// so stop pushing to pq, but collect remaining components
	int done_size = -1;
	ans.assign(n, 0);
	while (!roots.empty()) {
		auto [_, r] = roots.top();
		roots.pop();
		// find any outgoing edge
		bool has_outgoing = false;
		while (!out_can[r].empty()) {
			int to = out_can[r].back();
			out_can[r].pop_back();
			if (compressed.connected(r, to))
				continue;
			has_outgoing = true;
			if (done_size != -1) // we're larger than the answer
				break;
			if (weakly.connected(r, to)) {
				// merge with self. walk up parents 
				int j = compressed.tag(to);
				do {
					int jp = compressed.tag(par[j]);
					merge(j, jp);
					j = jp;
				} while (j != r);
				// we're still a root, but of larger size
				roots.push({ compressed.size(r), r });				
			} else { // merge with other component
				par[r] = to;
				weakly.connect(r, to);
				// we're no root any longer (no pq push)
			}
			break;
		}
		if (!has_outgoing) {
			int size = compressed.size(r);
			if (done_size != -1 && size != done_size)
				break;
			done_size = size;
			ans[r] = 1;
		}
	}
	for (int i = 0; i < n; i++) // everthing in their components too
		if (ans[compressed.tag(i)])
			ans[i] = 1;
}

vector<int> find_reachable(vector<int> r, vector<int> u,
		vector<int> v, vector<int> c) {
	n = r.size();
	for (int i = 0; i < n; i++)
		keys[i].insert(r[i]);
	for (size_t i = 0; i < u.size(); i++)
		for (int x = 0; x < 2; x++) {
			if (r[u[i]] == c[i])
				out_can[u[i]].push_back(v[i]);
			else
				out_blocked[u[i]].insert({ v[i], c[i] });
			swap(u[i], v[i]);
		}
	solve();
	return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33