Submission #1263018

#TimeUsernameProblemLanguageResultExecution timeMemory
1263018silentloopShortcut (IOI16_shortcut)C++20
0 / 100
2097 ms47380 KiB
#include <bits/stdc++.h> #define ll long long #define sz(x) int(x.size()) #define fr first #define se second #define pb push_back #define mp make_pair #define all(x) x.begin(),x.end() using namespace std; const int MAXN= 2000001; vector<pair<ll,ll>>grafo[MAXN]; ll N; vector<ll>dijk(ll nod) { priority_queue<pair<ll,ll>>pq; pq.push({0,nod}); ll i, n=N; vector<ll>proc(n*2+1,0),dist(n*2+1,LLONG_MAX); dist[nod]=0; while(pq.size()) { ll a=pq.top().se; pq.pop(); if(proc[a]) continue; proc[a]=1; for(auto k:grafo[a]) { if(dist[k.fr]>dist[a]+k.se) { dist[k.fr]=dist[a]+k.se; pq.push({-dist[k.fr],k.fr}); } } } return dist; } ll calc() { ll i, n=N, ma=0, j; for(i=0; i<n*2+1; i++) { vector<ll>dist=dijk(i); for(j=0; j<sz(dist); j++) { if(dist[j]==LLONG_MAX) continue; ma=max(dist[j],ma); } } return ma; } long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { N=n; ll i, j, mi=LLONG_MAX; for(i=0; i<sz(l); i++) { grafo[i].pb({i+1,l[i]}); grafo[i+1].pb({i,l[i]}); } for(i=0; i<n; i++) { if(d[i]>0) { grafo[i].pb({i+n,d[i]}); grafo[i+n].pb({i,d[i]}); } } for(i=0; i<n; i++) { for(j=i+1; j<n; j++) { grafo[i].pb({j,c}); grafo[j].pb({i,c}); mi=min(mi,calc()); grafo[i].pop_back(); grafo[j].pop_back(); } } return mi; }

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...