#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fixbug false
void SETIO(string name = ""){
if (name=="") return;
freopen((name+".inp").c_str(),"r",stdin);
// freopen((name+".out").c_str(),"w",stdout);
return;
}
#define ii pair<int,int>
#define x first
#define y second
const int maxn = 250000;
const int maxedge = 250000;
ii p[maxedge+2];
int n , k;
struct Node{
int d;
int x , y;
bool operator < (const Node& other) const{
if (d != other.d) return d < other.d;
if (x != other.x) return x < other.x;
return y < other.y;
}
};
vector<Node> edg;
int d(ii x , ii y){
return x.first - y.first + x.second - y.second;
}
void MST(){
vector<int> ids(n);
iota(ids.begin(),ids.end(),1);
for (int turn = 1; turn <= 4; ++turn){
sort(ids.begin(),ids.end(),[=](int i , int j){
return p[i].x+p[i].y < p[j].x+p[j].y;
});
map<int,int,greater<int>> active_set;
for (auto&i:ids){
for (auto it = active_set.lower_bound(p[i].x) ; it != active_set.end(); active_set.erase(it++)){
int j = it->second;
if (p[i].x-p[i].y > p[j].x-p[j].y) break;
edg.push_back({ d(p[i] , p[j]) , min(i,j) , max(i,j) });
}
active_set[p[i].x] = i;
}
for (auto& i : ids) {
if (turn&1) p[i].x *= -1; else swap(p[i].x,p[i].y);
}
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
SETIO("");
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
MST();
sort(edg.begin(),edg.end());
if (fixbug){
for (auto& x : edg) cout << x.d << ' ' << x.x << ' ' << x.y << '\n';
}
int i = 0 , cur = 0;
while (k--){
assert(i < edg.size());
cout << edg[i].d << '\n';
while (cur < edg.size() && edg[i].x == edg[cur].x && edg[i].y == edg[cur].y) ++cur;
i = cur;
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from road_construction.cpp:1:
road_construction.cpp: In function 'int main()':
road_construction.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | assert(i < edg.size());
| ~~^~~~~~~~~~~~
road_construction.cpp:75:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | while (cur < edg.size() && edg[i].x == edg[cur].x && edg[i].y == edg[cur].y) ++cur;
| ~~~~^~~~~~~~~~~~
road_construction.cpp: In function 'void SETIO(std::string)':
road_construction.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | freopen((name+".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
319 ms |
44416 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
393 ms |
20932 KB |
Output is correct |
| 2 |
Correct |
409 ms |
20708 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
393 ms |
20932 KB |
Output is correct |
| 2 |
Correct |
409 ms |
20708 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
