Submission #978099

#TimeUsernameProblemLanguageResultExecution timeMemory
978099nninJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
343 ms6096 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> int N, M, B[30005], P[30005]; int mindis[30005]; set<int> dog[30005]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>N>>M; for(int i=0;i<M;i++) { cin>>B[i]>>P[i]; dog[B[i]].insert(-P[i]); } for(int i=0;i<N;i++) { mindis[i] = 2e9; } priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, B[0]}); mindis[B[0]] = 0; while(!pq.empty()) { auto [dis, u] = pq.top(); pq.pop(); if(mindis[u]!=dis) continue; for(int pp:dog[u]) { int p = -pp; int v = u+p; int w = 1; while(v<N) { if(mindis[v]>dis+w){ mindis[v] = dis+w; pq.push({mindis[v], v}); } v += p; w++; } v = u-p; w = 1; while(v>=0) { if(mindis[v]>dis+w) { mindis[v] = dis+w; pq.push({mindis[v], v}); } v -= p; w++; } } } if(mindis[B[1]]==2e9) cout<<-1; else cout<<mindis[B[1]]; } /* 5 3 0 2 1 1 4 1 */
#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...