Submission #893438

#TimeUsernameProblemLanguageResultExecution timeMemory
893438vjudge1Road Construction (JOI21_road_construction)C++17
11 / 100
368 ms25516 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...