#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
#define pii pair<int,int>
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int N = 1e5 * 4 + 1;
vector<int>g[N];
const int inf = 1e16;
int n;
struct SegTree{
ar <int,2> T[N * 4];
SegTree(){
for ( int i = 0; i < N * 4; i++ ){
T[i] = {inf, -1};
}
}
void upd(int v, int l, int r, int pos, int val, int id){
if ( l == r ){
T[v] = {val, id};
return;
}
int md = (l + r) >> 1;
if ( pos > md ){
upd(v * 2 + 1, md + 1, r, pos, val, id);
} else{
upd(v * 2, l, md, pos, val, id);
}
T[v] = min(T[v * 2], T[v * 2 + 1]);
};
void upd(int pos, int val, int id){
upd(1, 0, n - 1, pos, val, id);
}
auto get(int v, int l, int r, int tl, int tr){
if ( l > tr or r < tl ){
return ar<int,2>{inf, -1};
}
if ( tl <= l && tr >= r ){
return T[v];
}
int md = (l + r) >> 1;
return min(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
}
auto get(int l, int r){
return get(1, 0, n - 1, l, r);
}
} s1, s2;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> n >> k;
vector<vector<int>>vsg(n+1,{0,0});
vector <ar<int,3>> a(n);
int ind = 0;
vector <int> pos;
for ( auto &[x, y, i]: a ){
cin >> x >> y;
vsg[ind][0] = x;
vsg[ind][1] = y;
i = ind++;
pos.pb(y);
}
sort(all(a)), sort(all(pos));
pos.resize(unique(all(pos)) - pos.begin());
auto get = [&](int u){
return lower_bound(all(pos), u) - pos.begin();
};
vector <int> opt(n, inf), ans(n);
{
for ( auto &[x, y, i]: a ){
int q = get(y);
auto [v1, j1] = s1.get(0, q);
v1 += x + y;
auto [v2, j2] = s2.get(q, n - 1);
v2 += x - y;
if ( v1 > v2 ){
swap(v1, v2), swap(j1, j2);
}
opt[i] = v1, ans[i] = j1;
if(0<=j1&&j1<n)
g[i].pb(j1);
if(0<=j2&&j2<n)
g[i].pb(j2);
s1.upd(q, -y - x, i);
s2.upd(q, -x + y, i);
}
}
for ( int i = 0; i < n; i++ ){
s1.upd(i, inf, -1);
s2.upd(i, inf, -1);
}
{
reverse(all(a));
for ( auto &[x, y, i]: a ){
int q = get(y);
auto [v1, j1] = s1.get(0, q);
v1 += -x + y;
auto [v2, j2] = s2.get(q, n - 1);
v2 += -x - y;
if ( v1 > v2 ){
swap(v1, v2), swap(j1, j2);
}
if(0<=j1&&j1<n)
g[i].pb(j1);
if(0<=j2&&j2<n)
g[i].pb(j2);
if ( chmin(opt[i], v1) ){
ans[i] = j1;
}
s1.upd(q, x - y, i);
s2.upd(q, x + y, i);
}
}
vector<int>u;
priority_queue <pair<int,pii>, vector <pair<int,pii>>, greater <pair<int,pii>> > q;
map<pii,int>mp;
for(int i = 0; i<n;i++){
mp[{i,i}] = 1;
for(auto to:g[i]){
if(mp[{i,to}]==1)continue;
q.push({abs(vsg[i][0] - vsg[to][0]) + abs(vsg[i][1]-vsg[to][1]),{i,to}});
mp[{i,to}] = 1;
mp[{to,i}] = 1;
//~ cout<<i<<" "<<to<<"\n";
}
}
while(u.size()<k){
auto [cost,x] = q.top();
q.pop();
//~ cout<<x.first<<"-"<<x.second<<endl;
u.pb(cost);
for(auto to:g[x.first]){
if(mp[{x.second,to}]==1)continue;
q.push({abs(vsg[x.second][0] - vsg[to][0]) + abs(vsg[x.second][1]-vsg[to][1]),{x.second,to}});
mp[{x.second,to}] = 1;
mp[{to,x.second}] = 1;
}
for(auto to:g[x.second]){
if(mp[{x.first,to}]==1)continue;
q.push({abs(vsg[x.first][0] - vsg[to][0]) + abs(vsg[x.first][1]-vsg[to][1]),{x.first,to}});
mp[{x.first,to}] = 1;
mp[{to,x.first}] = 1;
}
}
for(auto to:u)cout<<to<<"\n";
}
Compilation message
road_construction.cpp: In function 'int main()':
road_construction.cpp:167:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
167 | while(u.size()<k){
| ~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1123 ms |
100256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2371 ms |
202008 KB |
Output is correct |
| 2 |
Correct |
2354 ms |
201788 KB |
Output is correct |
| 3 |
Correct |
673 ms |
95848 KB |
Output is correct |
| 4 |
Correct |
1745 ms |
184308 KB |
Output is correct |
| 5 |
Correct |
1668 ms |
186980 KB |
Output is correct |
| 6 |
Correct |
1641 ms |
185360 KB |
Output is correct |
| 7 |
Correct |
2167 ms |
209544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2118 ms |
217664 KB |
Output is correct |
| 2 |
Correct |
2051 ms |
216944 KB |
Output is correct |
| 3 |
Correct |
10 ms |
59736 KB |
Output is correct |
| 4 |
Correct |
746 ms |
150416 KB |
Output is correct |
| 5 |
Correct |
1175 ms |
178568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2118 ms |
217664 KB |
Output is correct |
| 2 |
Correct |
2051 ms |
216944 KB |
Output is correct |
| 3 |
Correct |
10 ms |
59736 KB |
Output is correct |
| 4 |
Correct |
746 ms |
150416 KB |
Output is correct |
| 5 |
Correct |
1175 ms |
178568 KB |
Output is correct |
| 6 |
Correct |
2098 ms |
217228 KB |
Output is correct |
| 7 |
Correct |
2086 ms |
218684 KB |
Output is correct |
| 8 |
Correct |
9 ms |
59740 KB |
Output is correct |
| 9 |
Correct |
10 ms |
59908 KB |
Output is correct |
| 10 |
Correct |
2084 ms |
217704 KB |
Output is correct |
| 11 |
Correct |
749 ms |
150136 KB |
Output is correct |
| 12 |
Correct |
1222 ms |
179128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1123 ms |
100256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1123 ms |
100256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
