#include <bits/stdc++.h>
using namespace std;
// vector <int> a1, b1, c1, d1;
// void build(vector <int> a, vector <int> b, vector <int> c, vector <int> d) {
// a1 = a;
// b1 = b;
// c1 = c;
// d1 = d;
// }
const int N = 2e5 + 5;
int n;
vector <vector <int> > pos;
vector <int> a2, b2, c2, d2, par(N);
map <pair <int, int> , int> fIdx;
set <pair <int, int> > used;
int find(int a) {
if (par[a] == a) return a;
return par[a] = find(par[a]);
}
bool merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return 0;
par[b] = a;
return 1;
}
void connect(pair <int, int> pt, int i, int j) {
if (used.count(pt)) return;
used.insert(pt);
merge(i, j);
a2.push_back(i);
b2.push_back(j);
c2.push_back(pt.first);
d2.push_back(pt.second);
}
void xEdge(int x, int y) {
int X = x+1, Y = y + ((x+y)& 2 == 2 ? 1 : -1);
connect({X, Y}, fIdx[{x, y}], fIdx[{x+2, y}]);
}
void yEdge(int x, int y) {
int X = x + ((x+y)& 2 == 2 ? 1 : -1), Y = y+1;
connect({X, Y}, fIdx[{x, y}], fIdx[{x, y+2}]);
}
bool custom(vector<int>&a, vector<int>&b) {
return a < b;
}
int construct_roads(vector<int> X, vector<int> Y) {
n = X.size();
for (int i = 0; i < n; i++)
pos.push_back({X[i], Y[i], i});
sort(pos.begin(), pos.end(), custom);
for (int i = 0; i < n; i++) {
int id = pos[i][2];
pair <int, int> cur = {pos[i][0], pos[i][1]};
fIdx[cur] = id;
if (fIdx.count({cur.first-2, cur.second})) xEdge(cur.first-2, cur.second);
if (fIdx.count({cur.first, cur.second-2})) yEdge(cur.first, cur.second-2);
}
int source = find(0);
for (int i = 0; i < n; i++) {
cout << i << ": " << find(i) << '\n';
}
for (int i = 1; i < n; i++) {
if (source != find(i)) return 0;
}
build(a2, b2, c2, d2);
return 1;
}
// int main() {
// int n, a, b;
// freopen("in.txt", "r", stdin);
// cin >> n;
// vector <int> x, y;
// for (int i = 0; i < n; i++) {
// cin >> a >> b;
// x.push_back(a);
// y.push_back(b);
// }
// int val = construct_roads(x, y);
// cout << val << '\n';
// cout << a1.size() << '\n';
// for (int i = 0; i < a1.size(); i++) {
// cout << a1[i] << ' ' << b1[i] << ' ' << c1[i] << ' ' << d1[i] << '\n';
// }
// }
Compilation message
parks.cpp: In function 'void xEdge(int, int)':
parks.cpp:36:36: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
36 | int X = x+1, Y = y + ((x+y)& 2 == 2 ? 1 : -1);
| ~~^~~~
parks.cpp: In function 'void yEdge(int, int)':
parks.cpp:40:27: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
40 | int X = x + ((x+y)& 2 == 2 ? 1 : -1), Y = y+1;
| ~~^~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:65:5: error: 'build' was not declared in this scope
65 | build(a2, b2, c2, d2);
| ^~~~~
