제출 #1154313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154313		Newtonabc	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	1164 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
vector<pair<int,int>> adj[N];
int d[N];
bool ck[200][N];
//check if it has p[i] in that node already or not
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
vector<pair<int,int>> v;
bool vs[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,st,ed;
    cin>>n >>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>b >>a;
        if(i==0) st=b;
        if(i==1) ed=b;
        //p[i],pos[i]
        v.push_back({a,b});
    }
    if(n==1){
        cout<<-1;
        return 0;
    }
    //cout<<st <<" " <<ed <<"\n";
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(auto [pow,pos]:v){
        if(pow>190) break;
        ck[pow][pos]=true;
    }
    for(auto [pow,pos]:v){
        if(pow<=190){
            //forward
            for(int i=pos+pow;i<n;i+=pow){
                int tmp=(i-pos)/pow;
                adj[pos].push_back({i,tmp});
                if(ck[pow][i]) break;
                //cout<<pos <<" " <<i <<" " <<tmp <<"\n";
            }
            //backward
            for(int i=pos-pow;i>0;i-=pow){
                int tmp=(pos-i)/pow;
                adj[pos].push_back({i,tmp});
                if(ck[pow][i]) break;
                //cout<<pos <<" " <<i <<" " <<tmp <<"\n";
            }
        }
        else{
            //forward
            for(int i=pos+pow;i<n;i+=pow){
                int tmp=(i-pos)/pow;
                adj[pos].push_back({i,tmp});
            }
            //backward
            for(int i=pos-pow;i>0;i-=pow){
                int tmp=(pos-i)/pow;
                adj[pos].push_back({i,tmp});
            }
        }
    }
    for(int i=0;i<n;i++) d[i]=INT_MAX;
    d[st]=0;
    q.push({0,st});
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vs[u]) continue;
        vs[u]=true;
        for(auto [v,w]:adj[u]){
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                q.push({d[v],v});
            }
        }
    }
    if(d[ed]==INT_MAX) cout<<-1;
    else cout<<d[ed];
}

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