# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1083435 | _rain_ | Road Construction (JOI21_road_construction) | C++14 | 408 ms | 24128 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 , step = 0;
while (k>0){
if (i >= edg.size()) break;
cout << edg[i].d << '\n';
while (cur < edg.size() && edg[i].x == edg[cur].x && edg[i].y == edg[cur].y) ++cur;
i = cur;
--k;
}
while (k>0){
cout << edg.back().d << '\n';
--k;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |