#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]] && augemnt(match[v])) {
match[u] = v;
match[v] = u;
return true;
}
}
}
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 + nr; ++i) {
match[i] = -1;
}
while(true) {
bool any = false;
for(int i = 0; i < n + nr; ++i) {
vis[i] = false;
}
for(int i = 0; i < n + nr; ++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 'bool augument(int)':
parks.cpp:31:24: error: 'augemnt' was not declared in this scope; did you mean 'augument'?
31 | if(!vis[match[v]] && augemnt(match[v])) {
| ^~~~~~~
| augument
parks.cpp: In function 'int construct_roads(vi, vi)':
parks.cpp:97:25: error: 'nr' was not declared in this scope; did you mean 'n'?
97 | for(int i = 0; i < n + nr; ++i) {
| ^~
| n
parks.cpp:102:26: error: 'nr' was not declared in this scope; did you mean 'n'?
102 | for(int i = 0; i < n + nr; ++i) {
| ^~
| n
parks.cpp:105:26: error: 'nr' was not declared in this scope; did you mean 'n'?
105 | for(int i = 0; i < n + nr; ++i) {
| ^~
| n
parks.cpp:124:2: error: 'build' was not declared in this scope
124 | build(u,v,a,b);
| ^~~~~
parks.cpp: In function 'bool augument(int)':
parks.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
37 | }
| ^
