Submission #435365

#	Time	Username	Problem	Language	Result	Execution time	Memory
435365		fleimgruber	Fountain Parks (IOI21_parks)	C++17	70 / 100	1012 ms	130152 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;
	}
};
// ----------------
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

using Point = pair<int, int>;
set<Point> vis;
map<Point, int> all, fountain; // position => id
vector<int> X, Y;
vector<int> u, v;
vector<Point> v_fountain;

template<typename T> // set or map
bool has(T& set, int x, int y) {
	return set.find({ x, y }) != set.end();
}

int id_of_fountain(int x, int y) {
	if (!has(fountain, x, y)) {
		int id = fountain.size();
		fountain.insert({{ x, y }, id});
		v_fountain.push_back({ x, y });
		return id;
	}
	return fountain[{ x, y }];
}

int dfs(int i, int x, int y) {
	vis.insert({ x, y });
	int cnt = 1;
	for (auto [xp, yp] : vector<Point>{
			{ x+2, y }, { x-2, y }, { x, y+2 }, { x, y-2 }})
		if (has(all, xp, yp) && !has(vis, xp, yp)) {
			int j = all[{xp, yp}];
			u.push_back(i);
			v.push_back(j);
			cnt += dfs(j, xp, yp);
		}
	return cnt;
}

int construct_roads(vector<int> x_, vector<int> y_) {
	X = x_;
	Y = y_;
	int n = Y.size();
	for (int i = 0; i < n; i++)
		all.insert({{ X[i], Y[i] }, i});
	if (dfs(0, X[0], Y[0]) != n)
		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_fountain(x-1, y));
			g[i].push_back(id_of_fountain(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_fountain(x, y-1));
			g[i].push_back(id_of_fountain(x, y+1));
		}
	int m = fountain.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_fountain[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: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30