#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
typedef long long ll;
ll n;
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
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);
}
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: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]
56 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
parks.cpp:81: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]
81 | while (cnt < edges.size()) {
| ~~~~^~~~~~~~~~~~~~
parks.cpp:95: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]
95 | if (cnt < edges.size()) {
| ~~~~^~~~~~~~~~~~~~
parks.cpp:102: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]
102 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
parks.cpp:118: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]
118 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
parks.cpp:134: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]
134 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
