#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
vector<vector<int>> new_tree;
void dfs(int head, vector<vector<int>>&tree, vector<int> &vis){
vis[head] = true;
for(int i : tree[head]){
if(!vis[i]){
new_tree[head].push_back(i);
dfs(i, tree, vis);
}
}
}
int count_benches(vector<int> &c, map<pair<int,int>, int> &taken){
int s = 2;
if(c[0] != c[2]){
s -= taken[{c[0] - (c[0]-c[2])/2, c[1] + 1}];
s -= taken[{c[0] - (c[0]-c[2])/2, c[1] - 1}];
}
else{
s -= taken[{c[0] + 1, c[1] - (c[1] - c[3]) / 2}];
s -= taken[{c[0] - 1, c[1] - (c[1] - c[3]) / 2}];
}
return s;
}
int construct_roads(vector<int> x, vector<int> y){
int N = x.size();
vector<vector<int>> tree(N);
map<pair<int,int>, int> arr, bench, taken;
map<array<int, 4>, bool> road;
for(int i = 0; i < N; i ++){
arr[{x[i], y[i]}] = i;
}
vector<int> dx = {-2, 2, 0, 0}, dy = {0,0,2,-2};
for(int i = 0; i < N; i ++){
for(int j = 0; j < 4; j ++){
if(arr.find({x[i] + dx[j], y[i] + dy[j]}) != arr.end()){
tree[i].push_back(arr[{x[i] + dx[j], y[i] + dy[j]}]);
}
}
}
vector<pair<int, int>> pairs;
for(auto [l, r] : bench){
pairs.push_back(l);
}
sort(pairs.begin(), pairs.end(), [&](pair<int, int> a, pair<int, int> b){return bench[a] < bench[b];});
vector<int> vis(N, 0);
new_tree.resize(N);
dfs(0, tree, vis);
tree = new_tree;
for(int i = 0; i < N; i ++){
for(int j : tree[i]){
road[{x[i], y[i], x[j], y[j]}] = true;
road[{x[j], y[j], x[i], y[i]}] = true;
if(x[j] != x[i]){
bench[{(x[i] + x[j])/2, y[i] + 1}] ++;
bench[{(x[i] + x[j])/2, y[i] - 1}] ++;
}
if(y[j] != y[i]){
bench[{x[i] + 1, (y[i] + y[j]) / 2}] ++;
bench[{x[i] - 1, (y[i] + y[j]) / 2}] ++;
}
}
}
for(int i : vis){
if(!i){
return 0;
}
}
vector<int> ansu, ansv, ansa, ansb;
for(auto[l ,r] : pairs){
vector<int> dix = {1, -1, 1, -1}, diy = {-1, 1, 1, -1};
int bi = -1, bj = -1, s = 1e9;
for(int i = 0; i < 4; i ++){
for(int j = 0; j < 4; j ++){
int ss = 1e9;
if(road.find({l + dix[i], r + diy[i], l + dix[j], r + diy[j]}) != road.end()){
vector<int> tt = {l + dix[i], r + diy[i], l + dix[j], r + diy[j]};
ss = count_benches(tt, taken);
}
if(s > ss){
s = ss;
bi = i;
bj = j;
}
}
}
if(bi + 1){
road.erase({l + dix[bi], r + diy[bi], l + dix[bj], r + diy[bj]});
road.erase({l + dix[bj], r + diy[bj], l + dix[bi], r + diy[bi]});
ansu.push_back(arr[{l + dix[bi], r + diy[bi]}]);
ansv.push_back(arr[{l + dix[bj], r + diy[bj]}]);
ansa.push_back(l);
ansb.push_back(r);
taken[{l, r}] = true;
}
}
build(ansv, ansu, ansa, ansb);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
