Submission #351621

#TimeUsernameProblemLanguageResultExecution timeMemory
351621beksultan04Shortcut (IOI16_shortcut)C++14
0 / 100
2067 ms23936 KiB
#include "shortcut.h" #ifndef EVAL #include "grader.cpp" #endif // EVAL #include <bits/stdc++.h> using namespace std; #define lol long long #define pii pair<int,int> #define OK puts("OK"); #define NO puts("NO"); #define YES puts("YES"); #define fr first #define sc second #define ret return #define scanl(a) scanf("%lld",&a); #define scanll(a,b) scanf("%lld %lld",&a, &b); #define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c); #define scan1(a) scanf("%d",&a); #define scan2(a,b) scanf("%d %d",&a, &b); #define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c); #define all(s) s.begin(),s.end() #define allr(s) s.rbegin(),s.rend() #define pb push_back #define sz(v) (int)v.size() #define endi puts(""); #define eps 1e-12 const lol INF = 1e17+1; lol dia,iz,dis[1000001]; vector <pair<int,lol>> g[1000001]; lol find_shortcut(int n, vector<int> l, vector<int> d, int c){ int i,j,x=0,y=0,pos=0; lol ans = -1,mx = 0,res=INF; vector <pair<lol,pii> > v; for (i=0;i<n;++i){ g[i].pb({i+n,d[i]}); g[i+n].pb({i,d[i]}); if (i+1 < n){ g[i].pb({i+1,l[i]}); g[i+1].pb({i,l[i]}); } } for (x=0;x<n;++x){ for (y=x+1;y<n;++y){ ans = 0; g[x].pb({y,c}); g[y].pb({x,c}); for (int start = 0;start < 2*n;++start){ priority_queue <pair<lol,int>> s; for (i=0;i<n*2;++i)dis[i] = INF; s.push({0,start}); dis[start] = 0; while (!s.empty()){ int x = s.top().sc; s.pop(); for (pair<int,lol> to: g[x]){ if (to.sc+dis[x] < dis[to.fr]){ dis[to.fr] = to.sc+dis[x]; s.push({dis[to.fr],to.fr}); } } } for (i=0;i<n*2;++i){ if (dis[i] > ans && dis[i] != INF){ ans = dis[i]; } } } g[x].pop_back(); g[y].pop_back(); res = min(res,ans); } } ret res; }

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:32:11: warning: unused variable 'j' [-Wunused-variable]
   32 |     int i,j,x=0,y=0,pos=0;
      |           ^
shortcut.cpp:32:21: warning: unused variable 'pos' [-Wunused-variable]
   32 |     int i,j,x=0,y=0,pos=0;
      |                     ^~~
shortcut.cpp:33:18: warning: unused variable 'mx' [-Wunused-variable]
   33 |     lol ans = -1,mx = 0,res=INF;
      |                  ^~
#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...