oj.uz

답안 #520641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520641 2022-01-30T13:27:58 Z c28dnv9q3 열쇠 (IOI21_keys) C++17
100 / 100
 1063 ms 102636 KB 
// --- 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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 41388 KB Output is correct
2 Correct 19 ms 41292 KB Output is correct
3 Correct 18 ms 41360 KB Output is correct
4 Correct 19 ms 41332 KB Output is correct
5 Correct 18 ms 41332 KB Output is correct
6 Correct 19 ms 41320 KB Output is correct
7 Correct 20 ms 41360 KB Output is correct
8 Correct 19 ms 41320 KB Output is correct
9 Correct 22 ms 41420 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 41388 KB Output is correct
2 Correct 19 ms 41292 KB Output is correct
3 Correct 18 ms 41360 KB Output is correct
4 Correct 19 ms 41332 KB Output is correct
5 Correct 18 ms 41332 KB Output is correct
6 Correct 19 ms 41320 KB Output is correct
7 Correct 20 ms 41360 KB Output is correct
8 Correct 19 ms 41320 KB Output is correct
9 Correct 22 ms 41420 KB Output is correct
10 Correct 19 ms 41420 KB Output is correct
11 Correct 19 ms 41332 KB Output is correct
12 Correct 19 ms 41420 KB Output is correct
13 Correct 19 ms 41292 KB Output is correct
14 Correct 21 ms 41412 KB Output is correct
15 Correct 19 ms 41408 KB Output is correct
16 Correct 19 ms 41380 KB Output is correct
17 Correct 19 ms 41316 KB Output is correct
18 Correct 19 ms 41340 KB Output is correct
19 Correct 22 ms 41292 KB Output is correct
20 Correct 18 ms 41292 KB Output is correct
21 Correct 18 ms 41412 KB Output is correct
22 Correct 19 ms 41336 KB Output is correct
23 Correct 19 ms 41420 KB Output is correct
24 Correct 21 ms 41364 KB Output is correct
25 Correct 19 ms 41404 KB Output is correct
26 Correct 21 ms 41336 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 41388 KB Output is correct
2 Correct 19 ms 41292 KB Output is correct
3 Correct 18 ms 41360 KB Output is correct
4 Correct 19 ms 41332 KB Output is correct
5 Correct 18 ms 41332 KB Output is correct
6 Correct 19 ms 41320 KB Output is correct
7 Correct 20 ms 41360 KB Output is correct
8 Correct 19 ms 41320 KB Output is correct
9 Correct 22 ms 41420 KB Output is correct
10 Correct 19 ms 41420 KB Output is correct
11 Correct 19 ms 41332 KB Output is correct
12 Correct 19 ms 41420 KB Output is correct
13 Correct 19 ms 41292 KB Output is correct
14 Correct 21 ms 41412 KB Output is correct
15 Correct 19 ms 41408 KB Output is correct
16 Correct 19 ms 41380 KB Output is correct
17 Correct 19 ms 41316 KB Output is correct
18 Correct 19 ms 41340 KB Output is correct
19 Correct 22 ms 41292 KB Output is correct
20 Correct 18 ms 41292 KB Output is correct
21 Correct 18 ms 41412 KB Output is correct
22 Correct 19 ms 41336 KB Output is correct
23 Correct 19 ms 41420 KB Output is correct
24 Correct 21 ms 41364 KB Output is correct
25 Correct 19 ms 41404 KB Output is correct
26 Correct 21 ms 41336 KB Output is correct
27 Correct 20 ms 41712 KB Output is correct
28 Correct 20 ms 41676 KB Output is correct
29 Correct 20 ms 41640 KB Output is correct
30 Correct 20 ms 41548 KB Output is correct
31 Correct 19 ms 41420 KB Output is correct
32 Correct 19 ms 41380 KB Output is correct
33 Correct 20 ms 41548 KB Output is correct
34 Correct 20 ms 41500 KB Output is correct
35 Correct 23 ms 41532 KB Output is correct
36 Correct 23 ms 41584 KB Output is correct
37 Correct 23 ms 41628 KB Output is correct
38 Correct 24 ms 41676 KB Output is correct
39 Correct 20 ms 41644 KB Output is correct
40 Correct 20 ms 41524 KB Output is correct
41 Correct 20 ms 41660 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 41388 KB Output is correct
2 Correct 19 ms 41292 KB Output is correct
3 Correct 18 ms 41360 KB Output is correct
4 Correct 19 ms 41332 KB Output is correct
5 Correct 18 ms 41332 KB Output is correct
6 Correct 19 ms 41320 KB Output is correct
7 Correct 20 ms 41360 KB Output is correct
8 Correct 19 ms 41320 KB Output is correct
9 Correct 22 ms 41420 KB Output is correct
10 Correct 403 ms 81640 KB Output is correct
11 Correct 713 ms 102636 KB Output is correct
12 Correct 95 ms 51012 KB Output is correct
13 Correct 570 ms 88584 KB Output is correct
14 Correct 228 ms 81640 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 41388 KB Output is correct
2 Correct 19 ms 41292 KB Output is correct
3 Correct 18 ms 41360 KB Output is correct
4 Correct 19 ms 41332 KB Output is correct
5 Correct 18 ms 41332 KB Output is correct
6 Correct 19 ms 41320 KB Output is correct
7 Correct 20 ms 41360 KB Output is correct
8 Correct 19 ms 41320 KB Output is correct
9 Correct 22 ms 41420 KB Output is correct
10 Correct 19 ms 41420 KB Output is correct
11 Correct 19 ms 41332 KB Output is correct
12 Correct 19 ms 41420 KB Output is correct
13 Correct 19 ms 41292 KB Output is correct
14 Correct 21 ms 41412 KB Output is correct
15 Correct 19 ms 41408 KB Output is correct
16 Correct 19 ms 41380 KB Output is correct
17 Correct 19 ms 41316 KB Output is correct
18 Correct 19 ms 41340 KB Output is correct
19 Correct 22 ms 41292 KB Output is correct
20 Correct 18 ms 41292 KB Output is correct
21 Correct 18 ms 41412 KB Output is correct
22 Correct 19 ms 41336 KB Output is correct
23 Correct 19 ms 41420 KB Output is correct
24 Correct 21 ms 41364 KB Output is correct
25 Correct 19 ms 41404 KB Output is correct
26 Correct 21 ms 41336 KB Output is correct
27 Correct 20 ms 41712 KB Output is correct
28 Correct 20 ms 41676 KB Output is correct
29 Correct 20 ms 41640 KB Output is correct
30 Correct 20 ms 41548 KB Output is correct
31 Correct 19 ms 41420 KB Output is correct
32 Correct 19 ms 41380 KB Output is correct
33 Correct 20 ms 41548 KB Output is correct
34 Correct 20 ms 41500 KB Output is correct
35 Correct 23 ms 41532 KB Output is correct
36 Correct 23 ms 41584 KB Output is correct
37 Correct 23 ms 41628 KB Output is correct
38 Correct 24 ms 41676 KB Output is correct
39 Correct 20 ms 41644 KB Output is correct
40 Correct 20 ms 41524 KB Output is correct
41 Correct 20 ms 41660 KB Output is correct
42 Correct 403 ms 81640 KB Output is correct
43 Correct 713 ms 102636 KB Output is correct
44 Correct 95 ms 51012 KB Output is correct
45 Correct 570 ms 88584 KB Output is correct
46 Correct 228 ms 81640 KB Output is correct
47 Correct 21 ms 41292 KB Output is correct
48 Correct 19 ms 41420 KB Output is correct
49 Correct 19 ms 41324 KB Output is correct
50 Correct 213 ms 79472 KB Output is correct
51 Correct 209 ms 79468 KB Output is correct
52 Correct 286 ms 76508 KB Output is correct
53 Correct 272 ms 76592 KB Output is correct
54 Correct 292 ms 76616 KB Output is correct
55 Correct 425 ms 82364 KB Output is correct
56 Correct 357 ms 87660 KB Output is correct
57 Correct 288 ms 84292 KB Output is correct
58 Correct 575 ms 92844 KB Output is correct
59 Correct 1063 ms 88228 KB Output is correct
60 Correct 434 ms 87400 KB Output is correct
61 Correct 423 ms 86848 KB Output is correct
62 Correct 424 ms 83896 KB Output is correct
63 Correct 297 ms 85688 KB Output is correct
64 Correct 23 ms 42060 KB Output is correct
65 Correct 22 ms 42060 KB Output is correct
66 Correct 497 ms 83896 KB Output is correct
67 Correct 39 ms 45376 KB Output is correct
68 Correct 56 ms 48092 KB Output is correct
69 Correct 959 ms 88392 KB Output is correct
70 Correct 89 ms 54712 KB Output is correct
71 Correct 235 ms 82032 KB Output is correct
72 Correct 1045 ms 88372 KB Output is correct
73 Correct 504 ms 83812 KB Output is correct