Submission #1154330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154330		Newtonabc	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	223 ms	71392 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
vector<pair<int,int>> adj[N];
int d[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,a,b,tmp,u;
    cin>>n >>m;
    for(int i=0;i<m;i++){
        cin>>b >>a;
        if(i==0) st=b;
        if(i==1) ed=b;
        //p[i],pos[i]
        v.push_back({a,b});
    }
    if(m==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){
        //forward
        for(int i=pos+pow;i<n;i+=pow){
            tmp=(i-pos)/pow;
            adj[pos].push_back({i,tmp});
            if(*(lower_bound(v.begin(),v.end(),make_pair(pow,i)))==make_pair(pow,i)) break;
            //cout<<pos <<" " <<i <<" " <<tmp <<"\n";
        }
        //backward
        for(int i=pos-pow;i>=0;i-=pow){
            tmp=(pos-i)/pow;
            adj[pos].push_back({i,tmp});
            if(*(lower_bound(v.begin(),v.end(),make_pair(pow,i)))==make_pair(pow,i)) break;
            //cout<<pos <<" " <<i <<" " <<tmp <<"\n";
        }
    }
    for(int i=0;i<n;i++) d[i]=INT_MAX;
    d[st]=0;
    q.push({0,st});
    while(!q.empty()){
        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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43