#include "parks.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
struct DSU {
vi dad;
DSU(){}
DSU(int nn) {
dad.resize(nn);
for (int i =0 ;i<nn;i++) dad[i] = i;
}
int find(int x) {
if (x == dad[x]) return x;
return dad[x] = find(dad[x]);
}
bool unite(int a,int b) {
int x = find(a),y = find(b);
if (x == y) return false;
dad[x] = y;
return true;
}
} dsu;
vi x,y;
bool tryout(vector<pii> edgs) {
int n = edgs.size();
set<pii> benches[n];
map<pii,vi> useful;
for (int i = 0;i<n;i++) {
auto it = edgs[i];
pii p1 = {x[it.ff],y[it.ff]};
pii p2 = {x[it.ss],y[it.ss]};
if (p1.ff == p2.ff) {
benches[i] = {{p1.ff-1,max(p1.ss,p2.ss)-1},{p1.ff+1,max(p1.ss,p2.ss)-1}};
}
else {
benches[i] = {{max(p1.ff,p2.ff)-1,p1.ss-1},{max(p1.ff,p2.ff)-1,p1.ss+1}};
}
for (auto it : benches[i]) useful[it].push_back(i);
}
vi u(n),v(n),a(n,-1),b(n,-1);
for (int i = 0;i<n;i++) u[i] = edgs[i].ff,v[i] = edgs[i].ss;
set<int> ones,twos;
for (int i = 0;i<n;i++) twos.insert(i);
while (1) {
if (ones.size()) {
int fnd = *ones.begin();
ones.erase(fnd);
pii assign = *benches[fnd].begin();
a[fnd] = assign.ff,b[fnd] = assign.ss;
for (auto it : useful[assign]) {
if (it == fnd) continue;
if (big(benches[it]) == 2) ones.insert(it),twos.erase(it);
else if (big(benches[it]) == 1) ones.erase(it);
benches[it].erase(assign);
}
continue;
}
if (twos.empty()) break;
int fnd = *twos.begin();
twos.erase(fnd);
pii assign = *benches[fnd].begin();
a[fnd] = assign.ff,b[fnd] = assign.ss;
for (auto it : useful[assign]) {
if (it == fnd) continue;
if (big(benches[it]) == 2) ones.insert(it),twos.erase(it);
else if (big(benches[it]) == 1) ones.erase(it);
benches[it].erase(assign);
}
continue;
}
for (int i = 0;i<n;i++) if (a[i] == -1 || b[i] == -1) return false;
build(u,v,a,b);
return true;
}
int construct_roads(std::vector<int> xx, std::vector<int> yy) {
x = xx,y = yy;
int n = x.size();
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pii,int> id;
for (int i = 0;i<n;i++) {
id[{x[i],y[i]}] = i;
}
vi dx{2,0,-2,0},dy{0,2,0,-2};
dsu = DSU(n);
int con = 0;
vector<pii> edgs;
vi ord(n);
iota(all(ord),0ll);
sort(all(ord),[&](int a,int b){
return pii{x[a],y[a]}<pii{x[b],y[b]};
});
for (int i = 0;i<n;i++) {
for (int j = 0;j<4;j++){
if (id.count({x[i]+dx[j],y[i]+dy[j]})) {
if (dsu.unite(i,id[{x[i]+dx[j],y[i]+dy[j]}])) {
con++;
edgs.push_back({i,id[{x[i]+dx[j],y[i]+dy[j]}]});
}
}
}
}
if (con < n-1) return 0;
if (tryout(edgs)) return 1;
return 0;
}
