제출 #1275879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275879		hom84287	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	1096 ms	580 KiB

skyscraper

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

const int maxn = 3e4+123  , INF=1e9+7 ; 
priority_queue <pair<int,int> , vector <pair<int,int>> , greater<pair<int,int>> >dijks  ; 
vector <int> doge[maxn] ; 
int n , m ; 
int visited[maxn]  ;  

void dijk(int t){
    while(!dijks.empty()){
        auto [pay , ver] =dijks.top();
        dijks.pop() ;  
        if(ver==t){
            cout<<pay ; 
            return ; 
        } 
        if(visited[ver]==pay){
            //cout<<ver<<' '<<pay<<' ' ;
            for(int i:doge[ver]){
                for(int cnt=1+pay , verp=ver+i ; verp<n ; cnt++ , verp+=i){
                    if(visited[verp] > cnt) {
                        dijks.push({cnt , verp}) ;
                        visited[verp]=cnt ; 
                    }
                }
                for(int cnt=1+pay , verp=ver-i ; verp>=0 ; cnt++ , verp-=i){
                    if(visited[verp] > cnt) {
                        dijks.push({cnt , verp}) ;
                        visited[verp]=cnt ; 
                    }    
                } 
                doge[ver].clear() ; 
                doge[ver].shrink_to_fit(); 
            }
            //cout<<bfs.size()<<'\n'; 
        } 
    }
    cout<<-1 ;
}
int main(){
    cin>>n>>m ;
    fill(visited , visited+n+1 , INF) ; 
    int loc , p;  
    cin>>loc>>p ; 
    doge[loc].push_back(p) ;
    dijks.push({0,loc}) ;
    visited[loc]=0 ;  
    cin>>loc>>p ; 
    for(int i=2 ; i<m ;i++){
        int loco;
        cin>>loco>>p ;
        doge[loco].push_back(p) ;  
    }
    dijk(loc) ;
}

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