Submission #1275835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275835		hom84287	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	287 ms	327680 KiB

skyscraper

#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) ;  
    }
    for(int i=0 ; i<n ; i++){
        sort(doge[i].begin() , doge[i].end()) ; 
        unique(doge[i].begin() , 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: 0 / 43