제출 #1154304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154304		Newtonabc	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	863 ms	283856 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;
set<pair<int,pair<int,int>>> s;
set<pair<int,int>> ck;
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];
        if(ck.find({pos[i],p[i]})!=ck.end()) continue;
        ck.insert({pos[i],p[i]});
        for(int j=pos[i];j>=0;j-=p[i]){
            if(j==pos[i]) continue;
            if(s.find({pos[i],{j,(pos[i]-j)/p[i]}})!=s.end()) break;
            adj[pos[i]].push_back({j,(pos[i]-j)/p[i]});
            s.insert({pos[i],{j,(pos[i]-j)/p[i]}});
        }
        for(int j=pos[i];j<n;j+=p[i]){
            if(j==pos[i]) continue;
            if(s.find({pos[i],{j,(pos[i]-j)/p[i]}})!=s.end()) break;
            adj[pos[i]].push_back({j,(j-pos[i])/p[i]});
            s.insert({pos[i],{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: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43