#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
void dfs(int head, vector<vector<int>>&tree, vector<int> &vis){
vis[head] = true;
for(int i : tree[head]){
if(!vis[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]}]);
road[{x[i], y[i], x[i]+dx[j], y[i] + dy[j]}] = true;
road[{x[i]+dx[j], y[i] + dy[j], x[i], y[i]}] = true;
if(dx[j]){
bench[{x[i] + dx[j]/2, y[i] + 1}] ++;
bench[{x[i] + dx[j]/2, y[i] - 1}] ++;
}
if(dy[j]){
bench[{x[i] + 1, y[i] + dy[j] / 2}] ++;
bench[{x[i] - 1, y[i] + dy[j] / 2}] ++;
}
}
}
}
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);
dfs(0, tree, vis);
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()){
ss = count_benches({l + dix[i], r + diy[i], l + dix[j], r + diy[j]}, 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;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:70:95: error: cannot bind non-const lvalue reference of type 'std::vector<int>&' to an rvalue of type 'std::vector<int>'
70 | ss = count_benches({l + dix[i], r + diy[i], l + dix[j], r + diy[j]}, taken);
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/functional:62,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from parks.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:625:7: note: after user-defined conversion: 'std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<int>]'
625 | vector(initializer_list<value_type> __l,
| ^~~~~~
parks.cpp:12:32: note: initializing argument 1 of 'int count_benches(std::vector<int>&, std::map<std::pair<int, int>, int>&)'
12 | int count_benches(vector<int>& c, map<pair<int,int>, int> &taken){
| ~~~~~~~~~~~~~^
