Submission #1154228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154228		Newtonabc	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	453 ms	327680 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
vector<pair<int,int>> adj[N];
int pos[N],p[N],d[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
bool vs[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n >>m;
    for(int i=0;i<m;i++){
        cin>>pos[i] >>p[i];
        for(int j=pos[i];j>=0;j-=p[i]){
            if(j==pos[i]) continue;
            adj[pos[i]].push_back({j,(pos[i]-j)/p[i]});
        }
        for(int j=pos[i];j<n;j+=p[i]){
            if(j==pos[i]) continue;
            adj[pos[i]].push_back({j,(j-pos[i])/p[i]});
        }
    }
    int st=pos[0],ed=pos[1];
    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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43