Submission #1275965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275965		hom84287	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	454 ms	4952 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std  ; 

const int maxn = 3e4+123 ; 
const int INF=1e9+7 ; 
priority_queue <pair<int,int> , vector <pair<int,int>> , greater<pair<int,int>> >bfs  ; 
vector <int> doge[maxn] ; 
int n , m ; 
int 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]==pay){
            visited[ver]=pay ;
            for(int i:doge[ver]){
                    //cout<<i<<' ' ; 
                    for(int verp=ver+i ,cnt=1 ; verp<n ; verp += i , cnt++)  
                        if(visited[verp] > cnt+pay){ 
                            bfs.push({cnt + pay , verp}) ;
                            visited[verp]= cnt+pay ;  
                        }
                    for(int verp=ver-i , cnt=1 ; verp>=0 ; verp-=i , cnt++)
                        if(visited[verp] > cnt+pay){ 
                            bfs.push({cnt + pay , verp}) ;
                            visited[verp]= cnt+pay ;  
                        }
            } 
            doge[ver].clear() ; 
            doge[ver].shrink_to_fit(); 

        }
        //cout<<bfs.size()<<'\n'; 
    }
    cout<<-1 ; 
}
int main(){
    cin>>n>>m ;
    int loc , p; 
    fill(visited , visited+n+1 , INF)  ;
    cin>>loc>>p ; 
    doge[loc].push_back(p) ;
    visited[loc]=0 ; 
    bfs.push({0,loc}) ; 
    cin>>loc>>p ; 
    for(int i=2 ; i<m ;i++){
        int loco;
        cin>>loco>>p ;
        doge[loco].push_back(p) ;  
    }
    for(int i=0 ; i<n ; i++){
        sort(doge[i].begin() , doge[i].end()) ; 
        doge[i].erase(unique(doge[i].begin(), doge[i].end()), doge[i].end());
        doge[i].shrink_to_fit();  
        
    }
    BFS(loc) ;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43