#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
typedef long long ll;
ll n;
vector<ll> lnk;
vector<ll> sz;
ll find(ll a) {
if (a != lnk[a]) lnk[a] = find(lnk[a]);
return lnk[a];
}
bool unite(ll a, ll b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] > sz[b]) swap(a, b);
lnk[a] = b;
sz[b] += sz[a];
return true;
}
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
mt19937 mt(32523);
vector<pair<ll, ll>> coords(n);
for (int i = 0; i < n; i++) coords[i] = {x[i], y[i]};
shuffle(coords.begin(), coords.end(), mt);
for (int i = 0; i < n; i++) {
x[i] = coords[i].first;
y[i] = coords[i].second;
}
lnk = vector<ll>(n);
sz = vector<ll>(n, 1);
for (int i = 0; i < n; i++) lnk[i] = i;
unordered_map<ll, ll> pts;
vector<pair<ll, ll>> edges;
unordered_set<ll> hasEdge;
for (int i = 0; i < n; i++) {
ll hash = ((ll)x[i] << 31) | (ll)y[i];
pts[hash] = i;
}
for (ll i = 0; i < n; i++) {
ll hashL = (((ll)x[i]-2) << 31) | ((ll)y[i]);
if (pts.count(hashL)) {
ll hash = (min(i, pts[hashL]) << 31) | max(i, pts[hashL]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashL]});
hasEdge.insert(hash);
}
}
ll hashR = (((ll)x[i]+2) << 31) | ((ll)y[i]);
if (pts.count(hashR)) {
ll hash = (min(i, pts[hashR]) << 31) | max(i, pts[hashR]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashR]});
hasEdge.insert(hash);
}
}
ll hashD = (((ll)x[i]) << 31) | ((ll)y[i]-2);
if (pts.count(hashD)) {
ll hash = (min(i, pts[hashD]) << 31) | max(i, pts[hashD]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashD]});
hasEdge.insert(hash);
}
}
ll hashU = (((ll)x[i]) << 31) | ((ll)y[i]+2);
if (pts.count(hashU)) {
ll hash = (min(i, pts[hashU]) << 31) | max(i, pts[hashU]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashU]});
hasEdge.insert(hash);
}
}
}
unordered_map<ll, ll> poss;
unordered_map<ll, ll> lnk;
vector<pair<ll, ll>> edgeHashes(edges.size());
for (int i = 0; i < edges.size(); i++) {
auto e = edges[i];
ll midX = (x[e.first] + x[e.second]) / 2;
ll midY = (y[e.first] + y[e.second]) / 2;
ll leftX = midX - (midY - y[e.second]);
ll leftY = midY + (midX - x[e.second]);
ll rightX = midX + (midY - y[e.second]);
ll rightY = midY - (midX - x[e.second]);
ll hashL = (leftX << 31) | leftY;
ll hashR = (rightX << 31) | rightY;
poss[hashL]++;
poss[hashR]++;
lnk[hashL] ^= i;
lnk[hashR] ^= i;
edgeHashes[i] = {hashL, hashR};
}
vector<int> a(edges.size()), b(edges.size());
queue<ll> q;
for (auto &e : poss) {
if (e.second != 1) continue;
q.push(e.first);
}
ll cnt = 0;
unordered_set<ll> used;
while (cnt < edges.size()) {
while (!q.empty()) {
ll hash = q.front(); q.pop();
if (poss[hash] != 1 || used.count(hash)) continue;
cnt++;
ll id = lnk[hash];
a[id] = hash >> 31;
b[id] = hash & ~(1 << 31);
used.insert(id);
if (--poss[edgeHashes[id].first] == 1) q.push(edgeHashes[id].first);
if (--poss[edgeHashes[id].second] == 1) q.push(edgeHashes[id].second);
lnk[edgeHashes[id].first] ^= id;
lnk[edgeHashes[id].second] ^= id;
}
if (cnt < edges.size()) {
ll v = 0;
for (auto &e : poss) {
if (e.second != 2) continue;
v = e.first;
break;
}
for (int i = 0; i < edges.size(); i++) {
if (used.count(i)) continue;
auto e = edges[i];
ll midX = (x[e.first] + x[e.second]) / 2;
ll midY = (y[e.first] + y[e.second]) / 2;
if (abs(midX - (v >> 31)) + abs(midY - (v & ~(1 << 31))) > 1) continue;
a[i] = v >> 31;
b[i] = v & ~(1 << 31);
cnt++;
used.insert(i);
break;
}
//
poss.clear();
lnk.clear();
for (int i = 0; i < edges.size(); i++) {
if (used.count(i)) continue;
auto e = edges[i];
ll midX = (x[e.first] + x[e.second]) / 2;
ll midY = (y[e.first] + y[e.second]) / 2;
ll leftX = midX - (midY - y[e.second]);
ll leftY = midY + (midX - x[e.second]);
ll rightX = midX + (midY - y[e.second]);
ll rightY = midY - (midX - x[e.second]);
ll hashL = (leftX << 31) | leftY;
ll hashR = (rightX << 31) | rightY;
poss[hashL]++;
poss[hashR]++;
lnk[hashL] ^= i;
lnk[hashR] ^= i;
}
for (int i = 0; i < edges.size(); i++) {
if (!used.count(i)) continue;
ll hash = ((ll)a[i] << 31) | (ll)b[i];
poss[hash] = 0;
}
for (auto &e : poss) {
if (e.second != 1) continue;
q.push(e.first);
}
}
}
vector<int> u, v;
for (auto &e : edges) {
u.push_back(e.first);
v.push_back(e.second);
unite(e.first, e.second);
}
if (sz[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:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
parks.cpp:109:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while (cnt < edges.size()) {
| ~~~~^~~~~~~~~~~~~~
parks.cpp:123:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | if (cnt < edges.size()) {
| ~~~~^~~~~~~~~~~~~~
parks.cpp:130:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
parks.cpp:146:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
parks.cpp:162:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Pair u[0]=0 @(2, 2) and v[0]=2 @(2, 6) does not form a valid edge (distance != 2) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Pair u[0]=0 @(2, 2) and v[0]=2 @(2, 6) does not form a valid edge (distance != 2) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Pair u[0]=0 @(2, 2) and v[0]=2 @(2, 6) does not form a valid edge (distance != 2) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Pair u[0]=0 @(2, 2) and v[0]=2 @(2, 6) does not form a valid edge (distance != 2) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Pair u[0]=0 @(2, 2) and v[0]=2 @(2, 6) does not form a valid edge (distance != 2) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Pair u[0]=0 @(2, 2) and v[0]=2 @(2, 6) does not form a valid edge (distance != 2) |
| 5 |
Halted |
0 ms |
0 KB |
- |
