Submission #99520

#TimeUsernameProblemLanguageResultExecution timeMemory
99520ae04071Jakarta Skyscrapers (APIO15_skyscraper)C++11
57 / 100
1078 ms34232 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; using pii=pair<int,int>; map<pii,int> dp; priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> que; int n,m; vector<int> arr[30000]; inline int abs(int a) {return a<0 ? -a : a;} void push_val(int a,int b,int c) { if(a+b<0 || a+b>=n) return; pii idx = pii(a+b, abs(b)); if(!dp.count(idx) || dp[idx] > c) { dp[idx] = c; que.push({c,idx}); } } int main() { int ei; scanf("%d%d",&n,&m); for(int i=0,a,b;i<m;i++) { scanf("%d%d",&a,&b); arr[a].push_back(b); if(i==0) { dp[pii(a,0)]=0; que.push({0,{a,0}}); } else if(i==1) { ei = a; } } while(!que.empty()) { int cost=que.top().fi, pos=que.top().se.fi, pv=que.top().se.se; que.pop(); push_val(pos,-pv,cost+1); push_val(pos,pv,cost+1); while(!arr[pos].empty()) { int pp=arr[pos].back();arr[pos].pop_back(); push_val(pos-pp,pp,cost); } } int mx = -1; for(auto &v : dp) if(v.fi.fi==ei) { if(mx==-1 || mx > v.se) mx = v.se; } printf("%d\n",mx); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:49:23: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for(auto &v : dp) if(v.fi.fi==ei) {
                       ^~
#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...