#include <bits/stdc++.h>
//#include "parks.h"
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
class matching {
public:
vector< vector<int> > g;
vector<int> pa;
vector<int> pb;
vector<int> was;
int n, m;
int res;
int iter;
matching(int _n, int _m) : n(_n), m(_m) {
assert(0 <= n && 0 <= m);
pa = vector<int>(n, -1);
pb = vector<int>(m, -1);
was = vector<int>(n, 0);
g.resize(n);
res = 0;
iter = 0;
}
void add(int from, int to) {
assert(0 <= from && from < n && 0 <= to && to < m);
g[from].push_back(to);
}
bool dfs(int v) {
was[v] = iter;
for (int u : g[v]) {
if (pb[u] == -1) {
pa[v] = u;
pb[u] = v;
return true;
}
}
for (int u : g[v]) {
if (was[pb[u]] != iter && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int solve() {
while (true) {
iter++;
int add = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
add++;
}
}
if (add == 0) {
break;
}
res += add;
}
return res;
}
int run_one(int v) {
if (pa[v] != -1) {
return 0;
}
iter++;
return (int) dfs(v);
}
};
class dsu {
public:
vector<int> p;
int n;
dsu(){};
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
int construct_roads (vector<int> xvec, vector<int> yvec) {
int N = xvec.size();
map<pair<int, int>, int> to_v;
for (int i = 0; i < N; i++) {
to_v[make_pair(xvec[i], yvec[i])] = i;
}
auto get_v = [&](int X, int Y) {
if (to_v.count(make_pair(X, Y))) {
return to_v[make_pair(X, Y)];
}
return -1;
};
int n = 0;
vector<vector<int>> g;
map<pair<int, int>, int> to_face;
vector<pair<int, int>> bench;
auto get_face = [&](int X, int Y) {
if (to_face.count(make_pair(X, Y))) {
return to_face[make_pair(X, Y)];
}
bench.push_back({X, Y});
g.push_back({});
return to_face[make_pair(X, Y)] = n++;
};
int m = 0;
vector<int> node1, node2, face1, face2;
dsu fountain(N);
int is_connected = N;
auto make_edge = [&] (int x, int y, int X, int Y) {
int u = get_v(x, y), v = get_v(X, Y);
if (v == -1) {
return;
}
node1.push_back(u);
node2.push_back(v);
is_connected -= fountain.unite(u, v);
int f1, f2;
if (x == X) {
f1 = get_face(x + 1, (y + Y) / 2);
f2 = get_face(x - 1, (y + Y) / 2);
} else {
f1 = get_face((x + X) / 2, y + 1);
f2 = get_face((x + X) / 2, y - 1);
}
g[f1].push_back(m);
g[f2].push_back(m);
face1.push_back(f1);
face2.push_back(f2);
m++;
};
for (int i = 0; i < N; i++) {
int x = xvec[i], y = yvec[i];
make_edge(x, y, x + 2, y);
make_edge(x, y, x, y + 2);
}
if (is_connected > 1) {
return 0;
}
vector<int> removal(m);
vector<int> is_deg4(n);
for (int i = 0; i < n; i++) {
is_deg4[i] = g[i].size() == 4;
}
vector<vector<int>> nodes;
{
vector<set<int>> graph(n + 1);
for (int e = 0; e < m; e++) {
int u = face1[e], v = face2[e];
graph[u].insert(v);
graph[v].insert(u);
}
for (int i = 0; i < n; i++) {
if (graph[i].size() & 1) {
graph[i].insert(n);
graph[n].insert(i);
}
}
vector<int> way;
function<void(int)> dfs = [&](int v) {
vector<int> que = {v};
while (que.size()) {
int u = que.back();
if (graph[u].empty()) {
way.push_back(u);
que.pop_back();
} else {
int b = *graph[u].begin();
graph[u].erase(b);
graph[b].erase(u);
que.push_back(b);
}
}
};
vector<int> que;
vector<int> in_queue(n + 1);
for (int i = n; i >= 0; i--) {
if (graph[i].empty()) {
continue;
}
way.clear();
dfs(i);
for (int v : way) {
if (in_queue[v]) {
nodes.push_back({});
while (que.back() != v) {
nodes.back().push_back(que.back());
in_queue[que.back()] = 0;
que.pop_back();
}
nodes.back().push_back(v);
} else {
que.push_back(v);
in_queue[v] = 1;
}
}
que.pop_back();
in_queue[i] = 0;
}
}
int sz = nodes.size();
vector<vector<int>> edges;
{
map<pair<int, int>, int> cur;
for (int e = 0; e < m; e++) {
int u = face1[e], v = face2[e];
cur[make_pair(u, v)] = e;
cur[make_pair(v, u)] = e;
}
for (auto &p : nodes) {
edges.push_back({});
for (int i = 0; i < (int) p.size(); i++) {
int u = p[i], v = p[(i + 1) % p.size()];
if (cur.count(make_pair(u, v))) {
edges.back().push_back(cur[make_pair(u, v)]);
}
}
if (p.back() == n) {
p.pop_back();
}
}
}
vector<int> que;
vector<vector<int>> relaxed(n);
vector<int> was(sz);
for (int i = 0; i < sz; i++) {
for (int j : nodes[i]) {
relaxed[j].push_back(i);
}
bool ok = false;
for (int j : nodes[i]) {
if (!is_deg4[j]) {
ok = true;
}
}
if (ok) {
que.push_back(i);
was[i] = 1;
}
}
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
for (int j = 0; j < (int) edges[i].size(); j++) {
int v = nodes[i][j], e = edges[i][j];
if (is_deg4[v]) {
removal[e] = 1;
is_deg4[v] = 0;
for (int t : relaxed[v]) {
if (!was[t]) {
que.push_back(t);
was[t] = 1;
}
}
}
}
}
vector<int> paired(m, -1);
matching mt(m, n);
int cnt = m;
for (int e = 0; e < m; e++) {
if (removal[e]) {
cnt--;
continue;
}
mt.add(e, face1[e]);
mt.add(e, face2[e]);
}
vector<int> visited(n);
function<void(int, int)> dfs = [&] (int v, int ed) {
visited[v] = 1;
if (ed != -1) {
assert(mt.pa[ed] == -1);
mt.pa[ed] = v;
mt.pb[v] = ed;
mt.res++;
}
for (int e : g[v]) {
if (removal[e]) {
continue;
}
int u = face1[e] ^ face2[e] ^ v;
if (visited[u]) {
continue;
}
dfs(u, e);
}
};
for (int i = 0; i < n; i++) {
if (visited[i]) {
continue;
}
dfs(i, -1);
}
assert(mt.solve() == cnt);
for (int e = 0; e < m; e++) {
if (removal[e]) {
continue;
}
paired[e] = mt.pa[e];
}
vector<int> ru, rv, rx, ry;
for (int e = 0; e < m; e++) {
if (removal[e]) {
continue;
}
ru.push_back(node1[e]);
rv.push_back(node2[e]);
int id = paired[e];
rx.push_back(bench[id].first);
ry.push_back(bench[id].second);
}
build(ru, rv, rx, ry);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:436:3: error: 'build' was not declared in this scope
436 | build(ru, rv, rx, ry);
| ^~~~~
