/**
* author: wxhtzdy
* created: 21.07.2022 14:34:57
**/
/*
First idea was 2SAT having verteces (road, direction), but there always exist constructive idea...
https://oj.uz/submission/437652
*/
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {2, 0, -2, 0};
const int dy[] = {0, 2, 0, -2};
class dsu {
public:
vector<int> p;
int n;
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> x, vector<int> y) {
int n = (int) x.size();
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i++) {
mp[{x[i], y[i]}] = i;
}
vector<vector<int>> id(n, vector<int>(4, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
int nx = x[i] + dx[j];
int ny = y[i] + dy[j];
if (mp.count({nx, ny})) {
id[i][j] = mp[{nx, ny}];
}
}
}
dsu d(n);
vector<int> u, v;
vector<int> a, b;
auto Add = [&](int i, int j) {
d.unite(i, j);
u.push_back(i);
v.push_back(j);
if (x[i] == x[j]) {
b.push_back(y[i] + y[j] >> 1);
if ((x[i] + y[i]) % 2 == 1) {
a.push_back(x[i] - 1);
} else {
a.push_back(x[i] + 1);
}
} else {
a.push_back(x[i] + x[j] >> 1);
if ((x[i] + y[i]) % 2 == 1) {
b.push_back(y[i] + 1);
} else {
b.push_back(y[i] - 1);
}
}
};
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return x[i] + y[i] > x[j] + y[j];
});
for (int i : order) {
int i0 = id[i][0], i1 = id[i][1];
if (i0 == -1 && i1 == -1) {
continue;
}
if (i0 == -1) {
Add(i, i1);
continue;
}
if (i1 == -1) {
Add(i, i0);
continue;
}
if (d.get(i0) != d.get(i1)) {
Add(i, i0);
Add(i, i1);
} else {
if ((x[i] + y[i]) % 2 == 1) {
Add(i, i0);
} else {
Add(i, i1);
}
}
}
if ((int) u.size() != n - 1) {
return 0;
}
build(u, v, a, b);
return 1;
}
