Submission #1275763

#TimeUsernameProblemLanguageResultExecution timeMemory
1275763hom84287Jakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
402 ms327680 KiB
#include<bits/stdc++.h> using namespace std ; const int maxn = 3e4+123 ; priority_queue <pair<int,int> , vector <pair<int,int>> , greater<pair<int,int>> >bfs ; vector <int> doge[maxn] ; int n , m ; bool visited[maxn] ; //exitfrom[maxn][maxn]; void BFS(int t){ while(!bfs.empty()){ int pay=bfs.top().first , ver = bfs.top().second ; //cout<<ver<<' '<<pay<<' '<<t<<' ' ; if(ver==t){ cout<<pay ; return ; } bfs.pop() ; if(!visited[ver]){ visited[ver]=1 ; for(int i:doge[ver]){ //cout<<i<<' ' ; for(int verp=ver+i ,cnt=1 ; verp<n ; verp += i , cnt++) if(!visited[verp]) bfs.push({cnt + pay , verp}) ; for(int verp=ver-i , cnt=1 ; verp>=0 ; verp-=i , cnt++) if(!visited[verp]) bfs.push({cnt + pay , verp}) ; } doge[ver].clear() ; doge[ver].shrink_to_fit(); } //cout<<bfs.size()<<'\n'; } cout<<-1 ; } int main(){ cin>>n>>m ; int loc , p; for(int i=0 ; i<=n ;i++) doge[i].reserve(30000) ; cin>>loc>>p ; doge[loc].push_back(p) ; bfs.push({0,loc}) ; cin>>loc>>p ; for(int i=2 ; i<m ;i++){ int loco; cin>>loco>>p ; doge[loco].push_back(p) ; } BFS(loc) ; }
#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...