#include "parks.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second map<pii, int> id, got; vector<int> dsu, U, V, A, B; int fp(int a){ if (dsu[a]==-1)return a; return dsu[a]=fp(dsu[a]); } void merge(int aa, int bb, int x, int y){ int a=fp(aa), b=fp(bb); if (a==b||got[mp(x, y)])return; dsu[a]=b; A.pb(x); B.pb(y); U.pb(aa-1); V.pb(bb-1); got[mp(x, y)]=1; } int construct_roads(vector<int> x, vector<int> y){ int n=x.size(); dsu.resize(n+1, -1); vector<pii> ord; for (int i=1; i<=n; ++i){ id[mp(x[i-1], y[i-1])]=i; ord.pb(mp(x[i-1], y[i-1])); } sort(ord.begin(), ord.end()); for (auto c:ord){ int temp=(c.fi+c.se)%4; if (id[mp(c.fi, c.se-2)])merge(id[mp(c.fi, c.se-2)], id[mp(c.fi, c.se)], c.fi+(temp?1:-1), c.se-1); if (id[mp(c.fi-2, c.se)])merge(id[mp(c.fi-2, c.se)], id[mp(c.fi, c.se)], c.fi-1, c.se+(temp?-1:1)); } int cc=0; for (int i=1; i<=n; ++i)if (dsu[i]==-1)++cc; if (cc>1)return 0; build(U, V, A, B); return 1; }