// --- 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>;
set<Point> vis;
map<Point, int> all/*points in input*/, bench; // position => id
vector<int> X, Y;
vector<int> u, v;
vector<Point> v_bench;
template<typename T> // set or map
bool has(T& set, int x, int y) {
return set.find({ x, y }) != set.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() {
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;
}
}
// build spanning tree
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 false;
}
int construct_roads(vector<int> x_, vector<int> y_) {
X = x_;
Y = y_;
int n = X.size();
for (int i = 0; i < n; i++)
all.insert({{ X[i], Y[i] }, i});
if (!build_spanning_tree())
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
