Submission #682417

#TimeUsernameProblemLanguageResultExecution timeMemory
682417vjudge1Road Construction (JOI21_road_construction)C++17
38 / 100
6178 ms162116 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/rope> using namespace __gnu_cxx; // #pragma comment(linker, "/stack:2000000000") // #pragma GCC optimize("Ofast") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; #define precise(a) cout<<fixed<<setprecision(a) #define sz size() #define ff first #define ss second #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(), a.rend() #define pb push_back // t1 const ll mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6 const ll MOD = 998244353; // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod const ll N = ll(5e5)+10; const ll K = 17; const ll inf = 1e18; const ld eps = 1e-15L; //const ll B = 316; ll lcm(ll a, ll b){ return (a / __gcd(a,b)) * b; } //const ld P = acos(-1.0); // ll binpow(ll a, ll b, ll m){ ll res=1;a%=m; while(b>0){ if(b&1)res=(res*a)%m; a=(a*a)%m; b/=2; } return res%m;} ld binpow(ld a, ll b){ ld res=1; while(b>0){ if(b&1)res=(res*a); a=(a*a); b/=2; } return res;} void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); } void precalc() { } ll getdis(ll x1, ll y1, ll x2, ll y2) { return abs(x2-x1)+abs(y2-y1); } bool comp(pll a, pll b) { if(a.ff==b.ff) { return a.ss>=b.ss; } return a.ff<=b.ff; } void Baizho() { ll n, k; cin>>n>>k; pll a[n+11]; bool case2 = 1; for(ll i=1; i<=n; i++) { cin>>a[i].ff>>a[i].ss; if(a[i].ss!=0) case2 = 0; } sort(a+1, a+n+1, comp); set<pair<ll, pll> > st; if(n<=1000) { vector<ll>vec; for(ll i=1; i<=n-1; i++) { for(ll j=i+1; j<=n; j++) { ll x1 = a[i].ff, y1 = a[i].ss, x2 = a[j].ff, y2 = a[j].ss; ll dist = getdis(x1, y1, x2, y2); vec.pb(dist); } } sort(all(vec)); for(ll i=1; i<=k; i++) { cout<<vec[i-1]<<"\n"; } return; } for(ll i=1; i<=n-1; i++) { for(ll j=i+1; j<=i+10 && j<=n; j++) { ll x1 = a[i].ff, y1 = a[i].ss, x2 = a[j].ff, y2 = a[j].ss; ll dist = getdis(x1, y1, x2, y2); st.insert({dist, {i, j}}); } } for(ll i=1; i<=k; i++) { pair<ll, pll> get = (*st.begin()); cout<<get.ff<<"\n"; st.erase(get); if(get.ss.ss!=n) { for(ll j = get.ss.ss+1; j<=get.ss.ss+10 && j<=n; j++) { ll p = get.ss.ff; ll x1 = a[p].ff, y1 = a[p].ss, x2 = a[j].ff, y2 = a[j].ss; ll dist = getdis(x1, y1, x2, y2); st.insert({dist, {p, j}}); } } } } int main() { // Freopen("div7"); ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); precalc(); int ttt = 1; // cin>>ttt; for(int i=1; i<=ttt; i++) { Baizho();} }

Compilation message (stderr)

road_construction.cpp: In function 'void Baizho()':
road_construction.cpp:58:10: warning: variable 'case2' set but not used [-Wunused-but-set-variable]
   58 |     bool case2 = 1;
      |          ^~~~~
road_construction.cpp: In function 'void Freopen(std::string)':
road_construction.cpp:37:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:37:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...