#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<edge> construct_tree(){
vector<edge> ans;
dsu.init(n);
for(int i = 0; i < n; i++){
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}];
if(dsu.f(i) != dsu.f(v)){
dsu.g(i, v);
ans.push_back({i, v});
}
}
}
}
return ans;
}
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].x - 1}, {(a[u].x + a[v].x) / 2, a[v].x + 1}};
}
vector<point> assign_benches(vector<edge> roads){
vector<point> ans(roads.size());
map<point, vector<int>> deg;
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()){
cout << deg.size() << endl;
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(deg[v].size() != 1) continue;
int r = deg[v][0];
ans[r] = v;
int a = roads[r].u, b = roads[r].v;
vector<point> p = adj(a, b);
deg[p[0]].erase(find(all(deg[p[0]]), r));
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]);
}
if(deg.size()){
auto [c, v] = *deg.begin(); deg.erase(deg.begin());
if(v.empty()) continue;
assert((int) v.size() == 2);
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]].erase(find(all(deg[p[0]]), r));
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
