/**
* (Just a test)
*
* Time Complexity: O(n * log(n)) (Kruskal, bipartite graph, BFS, implementation)
* Implementation 0.9 (Just a test)
*/
#include <bits/stdc++.h>
#include "parks.h"
typedef std::vector<int> vec;
struct DSU {
vec set, rank;
DSU(int n) {
set.resize(n);
rank.resize(n);
for (int k = 0; k < n; k++)
set[k] = k, rank[k] = 1;
}
inline int find(int k) {
if (set[k] == k)
return k;
return set[k] = find(set[k]);
}
bool merge(int a, int b) {
a = find(a), b = find(b);
if (a == b)
return false;
if (rank[b] > rank[a])
std::swap(a, b);
set[b] = a, rank[a] += rank[b];
return true;
}
};
struct pos_t {
int x, y;
};
inline bool operator<(const pos_t& p1, const pos_t& p2) {
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
int construct_roads(vec x, vec y) {
int n = x.size();
std::map<pos_t, int> map;
for (int k = 0; k < n; k++)
map[{x[k], y[k]}] = k;
DSU dsu(n);
vec u(n - 1), v(n - 1);
int ans_pt = 0;
std::map<pos_t, vec> road_ls;
for (int k = 0; k < n; k++) {
for (int d = -1; d <= 1; d += 2) {
pos_t new_pos = {x[k], y[k] + 2 * d};
if (map.find(new_pos) == map.end())
continue;
int l = map[new_pos];
if (dsu.merge(k, l)) {
u[ans_pt] = k, v[ans_pt] = l;
road_ls[{x[k] - 1, y[k] + d}].push_back(ans_pt);
road_ls[{x[k] + 1, y[k] + d}].push_back(ans_pt);
ans_pt++;
}
}
}
vec order(n);
for (int i = 0; i < n; i++)
order[i] = i;
std::sort(order.begin(), order.end(),
[&](int o1, int o2) {
return y[o1] > y[o2];
});
for (int k : order) {
for (int d = -1; d <= 1; d += 2) {
pos_t new_pos = {x[k] + 2 * d, y[k]};
if (map.find(new_pos) == map.end())
continue;
int l = map[new_pos];
if (dsu.merge(k, l)) {
u[ans_pt] = k, v[ans_pt] = l;
road_ls[{x[k] + d, y[k] + 1}].push_back(ans_pt);
road_ls[{x[k] + d, y[k] - 1}].push_back(ans_pt);
ans_pt++;
}
}
}
if (ans_pt < n - 1)
return 0;
assert(ans_pt == n - 1);
vec bench_x(n - 1, -1), bench_y(n - 1, -1);
std::queue<int> bfs_queue;
for (int start = n - 2; start >= 0; start--) {
if (bench_x[start] != -1)
continue;
int s_u = u[start], s_v = v[start];
if (y[s_u] == y[s_v]) // horizontal
bench_x[start] = (x[s_u] + x[s_v]) / 2, bench_y[start] = y[s_u] + 1; // up
else
bench_x[start] = x[s_u] + 1, bench_y[start] = (y[s_u] + y[s_v]) / 2;
bfs_queue.push(start);
while (!bfs_queue.empty()) {
int t = bfs_queue.front(), bx = bench_x[t], by = bench_y[t];
bfs_queue.pop();
assert(bx != -1 && by != -1);
for (int nr : road_ls[{bx, by}]) {
if (bench_x[nr] != -1)
continue;
bench_x[nr] = x[u[nr]] + x[v[nr]] - bx;
bench_y[nr] = y[u[nr]] + y[v[nr]] - by;
bfs_queue.push(nr);
}
}
}
build(u, v, bench_x, bench_y);
return 1;
}
