#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int A[4] = {0, 0, 2, -2};
int B[4] = {2, -2, 0, 0};
array<int, 2> ben[4][2] = {{{-1, 1}, {1, 1}}, {{-1, -1}, {1, -1}}, {{1, 1}, {1, -1}}, {{-1, 1}, {-1, -1}}};
struct DSU
{
vector<int> e;
void init(int n)
{
e.assign(n, -1);
}
int get(int x)
{
if (e[x] < 0) return x;
return e[x] = get(e[x]);
}
void unite(int x, int y)
{
x = get(x), y = get(y);
if (x == y) return;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
}
};
int construct_roads(vector<int> X, vector<int> Y)
{
map<array<int, 2>, int> mp, us;
for (int i = 0; i < X.size(); i++) mp[{X[i], Y[i]}] = i + 1;
vector<int> u, v, a, b;
DSU dsu;
dsu.init(X.size());
for (int i = 0; i < X.size(); i++)
{
int x = X[i], y = Y[i];
for (int k = 0; k < 4; k++)
{
int x1 = x + A[k], y1 = y + B[k];
if (!mp[{x1, y1}] || mp[{x1, y1}] < i + 1) continue;
u.push_back(i), v.push_back(mp[{x1, y1}] - 1);
dsu.unite(i, mp[{x1, y1}] - 1);
for (array<int, 2> &j : ben[k])
{
int a1 = x + j[0], b1 = y + j[1];
if (!us[{a1, b1}])
{
a.push_back(a1);
b.push_back(b1);
break;
}
}
assert(a.size() == u.size());
}
}
for (int i = 0; i < n; i++)
{
if (dsu.get(i) != dsu.get(0)) 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:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0; i < X.size(); i++) mp[{X[i], Y[i]}] = i + 1;
| ~~^~~~~~~~~~
parks.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i = 0; i < X.size(); i++)
| ~~^~~~~~~~~~
parks.cpp:61:25: error: 'n' was not declared in this scope
61 | for (int i = 0; i < n; i++)
| ^
