Submission #1275838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275838		hom84287	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	2 ms	1352 KiB

skyscraper

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

const int maxn = 3e4+123 ; 

priority_queue <tuple<int,int,int> , vector <tuple<int,int,int>> , greater<tuple<int,int,int>> >bfs  ; 
vector <int> doge[maxn] ; 
int n , m ; 
bool visited[maxn] , vis[maxn][maxn]; 

void BFS(int t){
    while(!bfs.empty()){
        auto [pay , ver , dir] =bfs.top();
        bfs.pop() ;  
        //cout<<ver<<' '<<pay<<' '<<' '<<dir<<' '<<t<<"  " ;
        if(ver==t){
            cout<<pay ; 
            return ; 
        }   
        if(ver+dir>=0  && ver+dir<n ) if(!vis[ver+dir][abs(dir)]) bfs.push({1+pay , ver+dir , dir}) ; 
        if(!visited[ver]){
            visited[ver]=1 ;
            for(int i:doge[ver]){
                    //cout<<i<<' ' ;
                if((ver+i<n) && (ver+i>=0))  if(!visited[ver+i] && !vis[ver+i][i]){
                    bfs.push({1 + pay , ver+i , i}) ;
                } 
                if((ver-i>=0) && (ver-i<n))   if(!visited[ver-i] && !vis[ver-i][i]){
                    bfs.push({pay+1 , ver-i , -i}) ;
                } 
            } 
            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,n+100}) ; 
    cin>>loc>>p ; 
    for(int i=2 ; i<m ;i++){
        int loco;
        cin>>loco>>p ;
        doge[loco].push_back(p) ;  
    }
    BFS(loc) ;
}

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