Submission #60509

#TimeUsernameProblemLanguageResultExecution timeMemory
60509dukati8Jakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
664 ms7212 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i=a; i<int(b); i++) #define all(x) x.begin(),x.end() int main() { int n,m; cin >> n >> m; vector<pair<int,int> > doges(m); vector<set<int> > scrapers(n); //For each scraper a set of all dogs that reside there from beginning, or rather their jumps rep(i,0,m) { int b,p; cin >> b >> p; doges[i]=make_pair(b,abs(p)); scrapers[b].insert(-p); } queue<vector<int> > order; //Each element is <numjumps,position, jumplen, 1 or 0 for left/right> int dp[n]; rep (i,0,n) dp[i]=1000000000; int start,stop; start=doges[0].first; stop=doges[1].first; dp[start]=0; for (auto p:scrapers[start]) { order.push({0,start,-p,1}); order.push({0,start,-p,0}); } while (!order.empty()) { int num,pos,p; num=-order.front()[0]; pos=order.front()[1]; p=order.front()[2]; bool left = order.front()[3]==1; order.pop(); int next; if (left) next=pos+p; else next=pos-p; if (next>=0 && next<n) { if (next==stop) {dp[next]=min(num+1,dp[next]); break;} if (dp[next]>num+1) { dp[next]=num+1; for (auto pn:scrapers[next]){ if (-pn!=p) { order.push({-num-1,next,-pn,1}); order.push({-num-1,next,-pn,0}); } } } order.push({-num-1,next,p,left}); } } if (dp[stop] == 1000000000) cout << -1 << endl; else cout << dp[stop]<< endl; }
#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...