#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n';
#define ll long long int
const int N = 3e5+10;
struct Dsu{
vector<int> s, p;
Dsu(int n){
s.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return p[v] = find(p[v]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(s[a] > s[b]) swap(a, b);
p[a] = b;
s[b] += s[a];
}
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size();
vector<int> u, v, a, b;
Dsu d(n);
bool other = 0;
vector<pair<int, int>> L, R, M;
for(int i = 0; i < n; ++i){
if(x[i] == 2) L.pb({y[i], i});
else if(x[i] == 6) R.pb({y[i], i});
else if(x[i] == 4) M.pb({y[i], i});
else{
other = 1;
}
}
if(other){
map<pair<int, int>, int> m;
map<pair<int, int>, bool> used;
for(int i = 0; i < n; ++i) m[{x[i], y[i]}] = i + 1;
array<array<int, 2>, 4> A = {{2, 0}, {0, 2}, {-2, 0}, {0, -2}};
for(int i = 0; i < n; ++i){
for(int j = 0; j < 2; ++j){
int nx = A[j][0] + x[i], ny = A[j][1] + y[i];
int val = m[{nx, ny}];
if(val != 0){
d.merge(val - 1, i);
u.pb(i);
d.pb(val - 1);
int fx = A[j][0] == 0 ? x[i] + 1 : x[i] + A[j][0] / 2;
int fy = A[j][1] == 0 ? y[i] + 1 : y[i] + A[j][1] / 2;
if(used[{fx, fy}]){
if(A[j][0] == 0) fx = x[i] - 1;
else fy = y[i] - 1;
}
a.pb(fx);
b.pb(fy);
used[{fx, fy}] = 1;
}
}
}
}else{
sort(all(L));
sort(all(R));
sort(all(M));
for(int i = 0; i + 1 < L.size(); ++i){
if(L[i].first < L[i + 1].first - 2) continue;
u.pb(L[i].second);
v.pb(L[i + 1].second);
a.pb(1);
b.pb(L[i + 1].first + L[i].first>>1);
d.merge(L[i].second, L[i + 1].second);
}
for(int i = 0; i + 1 < R.size(); ++i){
if(R[i].first < R[i + 1].first - 2) continue;
u.pb(R[i].second);
v.pb(R[i + 1].second);
a.pb(7);
b.pb(R[i + 1].first + R[i].first>>1);
d.merge(R[i].second, R[i + 1].second);
}
for(int i = 0; i + 1 < M.size(); ++i){
if(M[i].first < M[i + 1].first - 2) continue;
u.pb(M[i].second);
v.pb(M[i + 1].second);
a.pb((M[i].first/2)%2 == 0 ? 5 : 3);
b.pb(M[i + 1].first + M[i].first>>1);
d.merge(M[i].second, M[i + 1].second);
}
int p = 0, last = -5;
for(int i = 0; i < M.size(); ++i){
while(p < R.size() && R[p].first < M[i].first) ++p;
if(p < R.size() && R[p].first == M[i].first){
if(last + 2 == M[i].first) continue;
last = M[i].first;
u.pb(R[p].second);
v.pb(M[i].second);
a.pb(5);
b.pb(M[i].first + ((M[i].first/2) % 2 == 0 ? -1 : 1));
d.merge(R[p].second, M[i].second);
}
}
p = 0, last = -5;
for(int i = 0; i < M.size(); ++i){
while(p < L.size() && L[p].first < M[i].first) ++p;
if(p < L.size() && L[p].first == M[i].first){
if(last + 2 == M[i].first) continue;
last = M[i].first;
u.pb(L[p].second);
v.pb(M[i].second);
a.pb(3);
b.pb(M[i].first + ((M[i].first/2) % 2 == 0 ? 1 : -1));
d.merge(L[p].second, M[i].second);
}
}
}
if(d.s[d.find(0)] < n) return 0;
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:56:70: error: too many initializers for 'std::array<std::array<int, 2>, 4>'
56 | array<array<int, 2>, 4> A = {{2, 0}, {0, 2}, {-2, 0}, {0, -2}};
| ^
parks.cpp:4:12: error: 'struct Dsu' has no member named 'push_back'
4 | #define pb push_back
| ^~~~~~~~~
parks.cpp:64:23: note: in expansion of macro 'pb'
64 | d.pb(val - 1);
| ^~
parks.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i = 0; i + 1 < L.size(); ++i){
| ~~~~~~^~~~~~~~~~
parks.cpp:86:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | b.pb(L[i + 1].first + L[i].first>>1);
parks.cpp:89:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0; i + 1 < R.size(); ++i){
| ~~~~~~^~~~~~~~~~
parks.cpp:94:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | b.pb(R[i + 1].first + R[i].first>>1);
parks.cpp:97:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i + 1 < M.size(); ++i){
| ~~~~~~^~~~~~~~~~
parks.cpp:102:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
102 | b.pb(M[i + 1].first + M[i].first>>1);
parks.cpp:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < M.size(); ++i){
| ~~^~~~~~~~~~
parks.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | while(p < R.size() && R[p].first < M[i].first) ++p;
| ~~^~~~~~~~~~
parks.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if(p < R.size() && R[p].first == M[i].first){
| ~~^~~~~~~~~~
parks.cpp:120:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i = 0; i < M.size(); ++i){
| ~~^~~~~~~~~~
parks.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | while(p < L.size() && L[p].first < M[i].first) ++p;
| ~~^~~~~~~~~~
parks.cpp:122:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if(p < L.size() && L[p].first == M[i].first){
| ~~^~~~~~~~~~
