Submission #435379

#	Time	Username	Problem	Language	Result	Execution time	Memory
435379		fleimgruber	Fountain Parks (IOI21_parks)	C++17	55 / 100	1161 ms	78612 KiB

parks

// --- algolib/bipartite-matching.h ---
// bipartite matching, that optionally finds the bipartition
// some of the functionality is enabled depending on FindBipartition, because
// in the !FindBipartition indices from left and right side coincide, making
// it impossible to provide reasonable return values
// if the graph is not bipartite, max_matching == -1. don't use the other
// functions in such cases.
// usage:
// 	- construct with either the adjacency list of a graph, or
//		((size left), (size right), adjacency list, containing only l -> r edges)
//	  for the ladder case, vertices are number [0..l[, [0..r[
// - access matching size using operator int()
// - access matched vertex using [vertex] (first constructor) or
//		partner(vertex, left_side)
// - if vertex numbers are distinct, reconstruct the min vertex cover (koenig's
//	 theorem) using min_vertex_cover()
#include <algorithm>
#include <type_traits>
#include <vector>

template<bool FindBipartition = true>
class MaxBipartiteMatching {
	using Graph = std::vector<std::vector<int>>;

	Graph e;
	int max_matching = 0;	
	std::vector<bool> vis, on_left;
	std::vector<int> match, left;

	bool dfs_bipartition(int i, bool is_left) { // false, if not bipartite
		vis[i] = true;
		on_left[i] = is_left;
		if (is_left)
			left.push_back(i);
		for (int j : e[i])
			if (!vis[j])
				dfs_bipartition(i, !is_left);
			else if (is_left == on_left[j])
				return false;
		return true;
	}

	bool augment(int i) {
		for (int j : e[i])
			if (!vis[j]) {
				vis[j] = true;
				if (match[j] == -1 || augment(match[j])) {
					match[i] = j;
					match[j] = i;
					return true;
				}
			}
		return false;
	}

	void find_matching() {
		int last;
		do {
			last = max_matching;
			if constexpr (FindBipartition) {
				std::fill(vis.begin(), vis.end(), false);
				for (int i : left)
					if (match[i] == -1)
						max_matching += augment(i);
			} else {
				int size_left = left[0];
				std::fill(vis.begin() + size_left, vis.end(), false);
				for (int i = 0; i < size_left; i++)
					if (match[i] == -1)
						max_matching += augment(i);
			}
		} while (max_matching > last);
	}

	void dfs_cover(int i) {
		vis[i] = true;
		for (int j : e[i])
			if (!vis[j] && match[i] != j) {
				vis[j] = true;
				if (int k = match[j]; k != -1 && !vis[k])
					dfs_cover(k);
			}
	}

public:
	// given any graph, finds bipartition and matching
	template<bool X = FindBipartition, typename std::enable_if_t<X, bool> = false>
	MaxBipartiteMatching(const Graph& e_) : e(e_), vis(e.size()),
		on_left(e.size()), match(e.size(), -1) {
		for (size_t i = 0; i < e.size(); i++) // bipartition
			if (!vis[i] && !dfs_bipartition(i, true)) {
				max_matching = -1;
				return;
			}
		find_matching();
	}
	
	// l vertices [0..l[ on the left, r vertices [0..r[ on the right
	// only left -> right edges given
	// in theory, a vis array of size r suffices. but in order to make the
	// code work with the other constructor, everything becomes terrible
	template<bool X = FindBipartition, typename std::enable_if_t<!X, bool> = true>	
	MaxBipartiteMatching(int l, int r, const Graph& e_) : e(e_), vis(l + r),
		match(l + r, -1) {
		left.push_back(l);
		for (auto& v : e) // shift [0..r[ by l
			for (int& i : v)
				i += l;
		find_matching(); // right -> left edges are not needed
	}

	// -1, if the graph is not bipartite
	operator int() { return max_matching; } // == size(min_vertex_cover)
	
	// Use either [left] or partner. returns -1 if there's no match
	template<bool X = FindBipartition>
	typename std::enable_if_t<X, int> operator[](int i) { return match[i]; }
	
	template<bool X = FindBipartition>
	typename std::enable_if_t<!X, int> partner(int i, bool left_side = true) {
		if (left_side) {
			int m = match[i];
			return m == -1 ? -1 : m - left[0];
		}
		return match[i + left[0]];
	}

	template<bool X = FindBipartition>
	typename std::enable_if_t<X, std::vector<int>> min_vertex_cover() {
		std::fill(vis.begin(), vis.end(), false);
		for (int i : left)
			if (match[i] == -1)
				dfs_cover(i);
		std::vector<int> cover;
		cover.reserve(max_matching);
		for (size_t i = 0; i < vis.size(); i++)
			if ((!on_left[i]) == vis[i])
				cover.push_back(i);
		return cover;
	}
};
// ----------------
// --- algolib/union-find.h ---
#include <algorithm>
#include <numeric>
#include <vector>

struct UnionFind {
	std::vector<int> p, size;

	UnionFind(int n) : 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); }
	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;
	}
};
// ----------------
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

using Point = pair<int, int>;
map<Point, int> all/*points in input*/, bench; // position => id
vector<Point> v_bench; // id => position
vector<int> u, v;

bool has(map<Point, int>& map, int x, int y) {
	return map.find({ x, y }) != map.end();
}

int id_of_bench(int x, int y) {
	if (!has(bench, x, y)) {
		int id = bench.size();
		bench.insert({{ x, y }, id});
		v_bench.push_back({ x, y });
		return id;
	}
	return bench[{ x, y }];
}

bool build_spanning_tree(vector<int>& X, vector<int>& Y) {
	int n = X.size();
	struct Edge {
		int i, j; // ids
		int weight;
	};
	vector<Edge> edges;
	for (int i = 0; i < n; i++) {
		int x = X[i], y = Y[i], cnt = 0;
		for (auto [xp, yp] : vector<Point>{{ x+2, y }, { x, y+2 }})
			if (has(all, xp, yp)) {
				cnt++;
				int j = all[{xp, yp}];
				edges.push_back({ i, j, 0 });
			}
		// 2x2 square => extra priority?
		if (cnt == 2 && has(all, x+2, y+2)) {
			edges[edges.size() - 2].weight = 2;
			edges[edges.size() - 1].weight = 1;
		}
	}
	// mst
	sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
		return a.weight > b.weight;
	});
	UnionFind dsu(n);
	for (auto [i, j, _] : edges)
		if (dsu.connect(i, j)) {
			u.push_back(i);
			v.push_back(j);
			if (int(u.size()) == n-1)
				return true;
		}
	return n == 1;
}

int construct_roads(vector<int> X, vector<int> Y) {
	int n = X.size();
	for (int i = 0; i < n; i++)
		all.insert({{ X[i], Y[i] }, i});
	if (!build_spanning_tree(X, Y))
		return 0;
	vector<vector<int>> g(n - 1); // left side = spanning tree edges
	for (int i = 0; i < n - 1; i++)
		if (X[u[i]] == X[v[i]]) { // vertical
			int x = X[u[i]], y = max(Y[u[i]], Y[v[i]]) - 1;
			g[i].push_back(id_of_bench(x-1, y));
			g[i].push_back(id_of_bench(x+1, y));
		} else { // horizontal
			int x = max(X[u[i]], X[v[i]]) - 1, y = Y[u[i]];
			g[i].push_back(id_of_bench(x, y-1));
			g[i].push_back(id_of_bench(x, y+1));
		}
	int m = bench.size();
	MaxBipartiteMatching<false> matching(n-1, m, g);
	if (matching != n-1)
		return 0;
	vector<int> a, b;
	for (int i = 0; i < n-1; i++) {
		auto [x, y] = v_bench[matching.partner(i)];
		a.push_back(x);
		b.push_back(y);
	}
	build(u, v, a, b);
	return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30