#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 400 * 1000 + 10;
map<pi, int>fontain;
pi road[nax];
int n;
vi V[nax], V2[nax];
map<pi, int>pts;
pi inv[nax];
bool vis[nax];
int match[nax];
bool augument(int u) {
vis[u] = true;
for(int v : V[u]) {
if(match[v] == -1) {
match[u] = v;
match[v] = u;
return true;
}
}
for(int v : V[u]) {
if(!vis[match[v]] && augument(match[v])) {
match[u] = v;
match[v] = u;
return true;
}
}
return false;
}
void dfs(int x) {
vis[x] = true;
for(int nbh : V2[x]) if(!vis[nbh]) {
dfs(nbh);
}
}
int construct_roads(vi xx, vi yx) {
for(int i = 0; i < (int)xx.size(); ++i) {
fontain[{xx[i], yx[i]}] = i;
}
for(auto it : fontain) {
auto [x, y] = it.ST;
if(fontain.count({x + 2, y})) {
road[n] = {it.ND, fontain[{x + 2, y}]};
pts[{x + 1, y - 1}];
pts[{x + 1, y + 1}];
n++;
}
if(fontain.count({x, y + 2})) {
road[n] = {it.ND, fontain[{x, y + 2}]};
pts[{x - 1, y + 1}];
pts[{x + 1, y + 1}];
n++;
}
}
int id = 0;
for(auto &it : pts) {
inv[id] = it.ST;
it.ND = id++;
}
for(int i = 0; i < n; ++i) {
V2[road[i].ST].PB(road[i].ND);
V2[road[i].ND].PB(road[i].ST);
int x1 = xx[road[i].ST], y1 = yx[road[i].ST];
int x2 = xx[road[i].ND], y2 = yx[road[i].ND];
if(x1 == x2) {
int y = (y1 + y2) / 2;
for(int x : {x1 - 1, x1 + 1}) {
int nr = pts[{x, y}];
V[i].emplace_back(n + nr);
V[n + nr].emplace_back(i);
}
} else if(y1 == y2) {
int x = (x1 + x2) / 2;
for(int y : {y1 - 1, y1 + 1}) {
int nr = pts[{x, y}];
V[i].emplace_back(n + nr);
V[n + nr].emplace_back(i);
}
}
}
dfs(0);
for(int i = 0; i < (int)xx.size(); ++i) {
if(!vis[i]) {
return 0;
}
}
for(int i = 0; i < n + id; ++i) {
match[i] = -1;
}
while(true) {
bool any = false;
for(int i = 0; i < n + id; ++i) {
vis[i] = false;
}
for(int i = 0; i < n + id; ++i) {
if(match[i] == -1 && augument(i)) {
any = true;
}
}
if(!any) break;
}
for(int i = 0; i < n; ++i) {
if(match[i] == -1) {
return 0;
}
}
vi u(n), v(n), a(n), b(n);
for(int i = 0; i < n; ++i) {
u[i] = road[i].ST;
v[i] = road[i].ND;
a[i] = inv[match[i]].ST;
b[i] = inv[match[i]].ND;
}
build(u,v,a,b);
return 1;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//}
Compilation message
parks.cpp: In function 'int construct_roads(vi, vi)':
parks.cpp:125:2: error: 'build' was not declared in this scope
125 | build(u,v,a,b);
| ^~~~~
