#include "parks.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int N_MAX = 2e5 + 11;
struct point{
int x, y;
bool operator< (const point& o) const {
return x < o.x || (x == o.x && y < o.y);
}
};
struct edge{
int u, v;
};
int n;
map<point, int> mp;
vector<point> a;
struct DSU{
int dsu[N_MAX];
void init(int n){
for(int i = 0; i < n; i++) dsu[i] = i;
}
int f(int x){ return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
void g(int x, int y){ x = f(x), y = f(y); dsu[x] = y; }
} dsu;
vector<point> adj(int u, int v){
assert(abs(a[u].x - a[v].x) + abs(a[u].y - a[v].y) == 2);
if(a[u].x == a[v].x) return {{a[u].x - 1, (a[u].y + a[v].y) / 2}, {a[u].x + 1, (a[u].y + a[v].y) / 2}};
else return {{(a[u].x + a[v].x) / 2, a[v].y - 1}, {(a[u].x + a[v].x) / 2, a[v].y + 1}};
}
vector<edge> construct_tree(){
vector<edge> ans;
dsu.init(n);
vector<int> p; for(int i = 0; i < n; i++) p.push_back(i);
sort(p.begin(), p.end(), [](int u, int v){ return a[u] < a[v]; });
set<point> used;
for(int j = 0; j < n; j++){
int i = p[j];
for(auto [dx, dy] : (a[i].x + a[i].y) % 4 ? vector<pair<int, int>>{{2, 0}, {0, 2}} : vector<pair<int, int>>{{0, -2}, {-2, 0}}){
int nx = a[i].x + dx, ny = a[i].y + dy;
if(mp.count({nx, ny})){
int v = mp[{nx, ny}];
ans.push_back({i, v});
dsu.g(i, v);
if(a[i].x == nx){
used.insert({nx - 1, (a[i].y + ny) / 2});
}else{
used.insert({(a[i].x + nx) / 2, ny + 1});
}
}
}
}
for(int j = 0; j < n; j++){
int i = p[j];
for(auto [dx, dy] : vector<pair<int, int>>{{0, -2}, {0, 2}, {2, 0}, {-2, 0}}){
int nx = a[i].x + dx, ny = a[i].y + dy;
if(mp.count({nx, ny})){
int v = mp[{nx, ny}];
vector<point> p = adj(i, v);
if(used.count(p[0]) && used.count(p[1])) continue;
if(dsu.f(i) != dsu.f(v)){
dsu.g(i, v);
ans.push_back({i, v});
}
}
}
}
return ans;
}
vector<point> assign_benches(vector<edge> roads){
vector<point> ans(roads.size());
map<point, vector<int>> deg;
set<point> done;
for(int i = 0; i < (int) roads.size(); i++){
int u = roads[i].u, v = roads[i].v;
vector<point> p = adj(u, v);
deg[p[0]].push_back(i);
deg[p[1]].push_back(i);
}
vector<point> deg_0, deg_1;
for(auto [p, v] : deg){
if(v.size() == 0) deg_0.push_back(p);
if(v.size() == 1) deg_1.push_back(p);
}
while(deg.size()){
while(deg_0.size()) deg.erase(deg_0.back()), deg_0.pop_back();
while(deg_1.size()){
point v = deg_1.back(); deg_1.pop_back();
if(done.count(v) || deg[v].empty()) continue; done.insert(v);
int r = deg[v][0];
ans[r] = v;
int a = roads[r].u, b = roads[r].v;
vector<point> p = adj(a, b);
if(find(all(deg[p[0]]), r) != deg[p[0]].end()) deg[p[0]].erase(find(all(deg[p[0]]), r));
if(find(all(deg[p[1]]), r) != deg[p[1]].end()) deg[p[1]].erase(find(all(deg[p[1]]), r));
if(deg.count(p[0]) && deg[p[0]].size() == 0) deg_0.push_back(p[0]);
if(deg.count(p[0]) && deg[p[0]].size() == 1) deg_1.push_back(p[0]);
if(deg.count(p[1]) && deg[p[1]].size() == 0) deg_0.push_back(p[1]);
if(deg.count(p[1]) && deg[p[1]].size() == 1) deg_1.push_back(p[1]);
}
if(deg.size()){
auto [c, v] = *deg.begin();
if(done.count(c) || deg[c].size() < 2){
deg.erase(deg.begin());
continue;
}
done.insert(c);
int r = v[0];
ans[r] = c;
int a = roads[r].u, b = roads[r].v;
vector<point> p = adj(a, b);
deg[p[0]].clear();
if(find(all(deg[p[1]]), r) != deg[p[1]].end()) deg[p[1]].erase(find(all(deg[p[1]]), r));
if(deg[p[0]].size() == 0) deg_0.push_back(p[0]);
if(deg[p[0]].size() == 1) deg_1.push_back(p[0]);
if(deg[p[1]].size() == 0) deg_0.push_back(p[1]);
if(deg[p[1]].size() == 1) deg_1.push_back(p[1]);
}
}
return ans;
}
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
for(int i = 0; i < n; i++){
a.push_back({x[i], y[i]});
mp[a[i]] = i;
}
vector<edge> edges = construct_tree();
if((int) edges.size() < n - 1) return 0;
vector<point> benches = assign_benches(edges);
vector<int> u(n - 1), v(n - 1), a(n - 1), b(n - 1);
for(int i = 0; i < n - 1; i++){
u[i] = edges[i].u, v[i] = edges[i].v;
a[i] = benches[i].x, b[i] = benches[i].y;
}
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'std::vector<point> assign_benches(std::vector<edge>)':
parks.cpp:97:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
97 | if(done.count(v) || deg[v].empty()) continue; done.insert(v);
| ^~
parks.cpp:97:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
97 | if(done.count(v) || deg[v].empty()) continue; done.insert(v);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Edge between 2 and 1 appears more than once: appeared on positions 0 and 1 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Edge between 2 and 1 appears more than once: appeared on positions 0 and 1 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Edge between 2 and 1 appears more than once: appeared on positions 0 and 1 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Edge between 2 and 1 appears more than once: appeared on positions 0 and 1 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Edge between 2 and 1 appears more than once: appeared on positions 0 and 1 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Edge between 2 and 1 appears more than once: appeared on positions 0 and 1 |
| 5 |
Halted |
0 ms |
0 KB |
- |
