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 pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
///* __ __ __ */
///* ====== _ /| /| __ _ / | | /| | @ | | | | / /| |\ | / | | @ | / */
///* \- || |_| |_ / |/ | | | |_ |- | |--| /-| | | \ \ |==| |- /=| | \ | | |--| | |- */
///* || | | |_ / | |__| _| |_ \__ | | / | |__ | __| | | | \ / | | \| \__ | | | | \ */
///*
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
void solve(){
int n, k;
cin >> n >> k;
if(n*n < 1e9){
vii v(n);
vi ans;
for(auto &[i,j]:v)cin >> i >> j;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
ans.pb(abs(v[i].ff-v[j].ff)+abs(v[i].ss-v[j].ss));
}
}sort(all(ans));
for(int i = 0; i < k; i++)cout << ans[i] << '\n';
}else if(k == 1){
}else{
vii v(n);
for(auto &[i, j]:v)cin >> i >> j;
sort(all(v));
multiset<pii> st;
vi df, ans;
for(int i = 0; i < n-1; i++){
df.pb(abs(v[i].ff-v[i+1].ff)+abs(v[i].ss-v[i+1].ss));
}
for(int i = 0; i < n-1; i++){
st.insert({df[i], i+1});
}
while((int)ans.size() < k){
auto [cost, i] = *st.begin();
st.erase(*st.begin());
ans.pb(cost);
if(i < n-1){
st.insert({cost+df[i], i+1});
}
}
sort(all(ans));
for(int i = 0; i < k; i++){
cout << ans[i] << '\n';
}
}
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int test = 1;
//~ cin >> test;
while(test--){
solve();
}
}
Compilation message (stderr)
road_construction.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
58 | main(){
| ^~~~
# | 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... |