#include <bits/stdc++.h>
#include "parks.h"
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
struct dsu {
vector<int> p, size;
dsu(int n) : p(n), size(n, 1) {
iota(all(p), 0);
}
int get(int v) {
return v == p[v] ? v : p[v] = get(p[v]);
}
bool merge(int a, int b) {
a = get(a), b = get(b);
if (a == b) return 0;
if (size[a] < size[b]) swap(a, b);
size[a] += size[b], p[b] = a;
return 1;
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = sz(x);
map<ar<int, 4>, int> mp;
map<ar<int, 2>, int> idx;
for (int i = 0; i < n; i++) idx[{x[i], y[i]}] = i;
map<ar<int, 2>, int> adj;
for (int i = 0; i < n; i++) {
if (idx.count({x[i] + 2, y[i]})) {
mp[{x[i], y[i], x[i] + 2, y[i]}] += 2;
adj[{x[i] + 1, y[i] + 1}]++;
adj[{x[i] + 1, y[i] - 1}]++;
}
if (idx.count({x[i], y[i] + 2})) {
mp[{x[i], y[i], x[i], y[i] + 2}] += 2;
adj[{x[i] + 1, y[i] + 1}]++;
adj[{x[i] - 1, y[i] + 1}]++;
}
}
set<pair<int, ar<int, 2>>> q;
for (auto [x, y] : adj) q.insert({y, x});
dsu D(n);
vector<int> a(n-1), b(n-1), c(n-1), d(n-1);
set<ar<int, 2>> used;
int now = 0;
while (q.size()) {
auto [val, p] = *q.begin();
q.erase(q.begin());
if (val != adj[p]) {
if (adj[p]) {
q.insert({adj[p], p});
continue;
}
}
ar<int, 4> seg2{p[0] - 1, p[1] - 1, p[0] - 1, p[1] + 1};
ar<int, 4> seg3{p[0] + 1, p[1] - 1, p[0] + 1, p[1] + 1};
ar<int, 4> seg4{p[0] - 1, p[1] - 1, p[0] + 1, p[1] - 1};
ar<int, 4> seg5{p[0] - 1, p[1] + 1, p[0] + 1, p[1] + 1};
bool F = 0;
for (auto& seg : {seg2, seg3, seg4, seg5}) if (mp.count(seg) && mp[seg] == 1) {
int i1 = idx[{seg[0], seg[1]}], i2 = idx[{seg[2], seg[3]}];
if (D.get(i1) == D.get(i2)) continue;
F = 1;
D.merge(i1, i2);
a[now] = i1, b[now] = i2;
c[now] = p[0], d[now] = p[1];
now++;
ar<int, 2> pt, pt2;
if (seg[0] != seg[2]) {
pt = {seg[0] + 1, seg[1] - 1};
pt2 = {seg[0] + 1, seg[1] + 1};
}
else {
pt = {seg[0] - 1, seg[1] + 1};
pt2 = {seg[0] + 1, seg[1] + 1};
}
for (auto p : {pt, pt2}) adj[p]--;
break;
}
if (!F) {
for (auto& seg : {seg2, seg3, seg4, seg5}) if (mp.count(seg) && mp[seg] == 2) {
int i1 = idx[{seg[0], seg[1]}], i2 = idx[{seg[2], seg[3]}];
if (D.get(i1) == D.get(i2)) continue;
F = 1;
D.merge(i1, i2);
a[now] = i1, b[now] = i2;
c[now] = p[0], d[now] = p[1];
now++;
ar<int, 2> pt, pt2;
if (seg[0] != seg[2]) {
pt = {seg[0] + 1, seg[1] - 1};
pt2 = {seg[0] + 1, seg[1] + 1};
}
else {
pt = {seg[0] - 1, seg[1] + 1};
pt2 = {seg[0] + 1, seg[1] + 1};
}
for (auto p : {pt, pt2}) adj[p]--;
break;
}
}
assert(F);
for (auto& seg : {seg2, seg3, seg4, seg5}) mp[seg]--;
}
if (D.size[D.get(0)] != n) return 0;
build(a, b, c, d);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
