제출 #1187358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187358		Warinchai	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	165 ms	193420 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
map<pair<short,short>,vector<short>>mp;
vector<int> up[5000005];
int down1[5000005],down2[5000005],hor[5000005];
vector<int>dis;
int inf=1e9;
int have[5000005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    if(n>3e4)for(int i=0;i<n;i);
    //assert(n<=3e4);
    int st=0,en=0;
    for(int i=0;i<m;i++){
        int b,p;cin>>b>>p;
        if(i==0)st=b;
        if(i==1)en=b;
        if(i!=1)mp[{b%p,p}].push_back(b);
        have[b]++;
    }
    int id=n-1;
    for(int i=0;i<=2e6;i++)down1[i]=down2[i]=hor[i]=-1;
    for(auto x:mp){
        int cur=x.first.first;
        int p=x.first.second;
        for(auto b:x.second)up[b].push_back(id+(b-cur)/p+1);
        for(cur;cur<n;cur+=p){
            id++;
            if(have[cur])down1[id]=cur;
            if(cur!=x.first.first)hor[id-1]=id;
        }
        cur=x.first.first;
        for(auto b:x.second)up[b].push_back(id+(b-cur)/p+1);
        for(cur;cur<n;cur+=p){
            id++;
            if(have[cur])down2[id]=cur;
            if(cur!=x.first.first)hor[id]=id-1;
        }
    }
    //assert(id<2e6);
    dis.resize(id+1,inf);
    mp.clear();
    deque<pair<int,int>>dq;
    dq.push_back({0,st});
    while(!dq.empty()){
        auto [d,u]=dq.front();
        //assert(u<2e6);
        dq.pop_front();
        if(d>=dis[u])continue;
        dis[u]=d;
        //assert(u<2e6);
        if(u==en)break;
        if(u<n)for(auto x:up[u])dq.push_front({d,x});
        /*for(auto x:down1[u])dq.push_front({d,x});
        for(auto x:down2[u])dq.push_front({d,x});
        for(auto x:hor[u])dq.push_back({d+1,x});*/
        if(down1[u]!=-1)dq.push_front({d,down1[u]});
        if(down2[u]!=-1)dq.push_front({d,down2[u]});
        if(hor[u]!=-1)dq.push_back({d+1,hor[u]});
    }
    if(dis[en]==inf)cout<<-1;
    else cout<<dis[en];
}

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