Submission #995816

#	Time	Username	Problem	Language	Result	Execution time	Memory
995816		ian0704	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	519 ms	3532 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define inf 1e9
int n,m;
int st,en;
int d[30010];
vector<int> v[30010];
void go()
{
    fill(d,d+n+1,inf);
    d[st]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,st});
    while(!pq.empty())
    {
        pair<int,int> a=pq.top();
        int current=a.second;
        int distance=-a.first;
        //cout<<"| "<<current<<" "<<distance<<'\n';
        pq.pop();
        if(d[current]<distance) continue;
        for(auto j:v[current])
        {
            int num=1;
            while(1)
            {
                int temp=current+j*num;
                //cout<<d[current];
                if(temp>=n) break;
                if(distance+num<d[temp])
                {
                    d[temp]=distance+num;
                    pq.push({-d[temp],temp});
                    if(v[temp].size())
                    {
                        int idx=upper_bound(v[temp].begin(),v[temp].end(),j)-v[temp].begin();
                        if(v[temp][idx-1]==j) break;                        
                    }
                }
                num++;
            }
            num=1;
            while(1)
            {
                int temp=current-j*num;
                if(temp<0) break;
                if(distance+num<d[temp])
                {
                    d[temp]=distance+num;
                    pq.push({-d[temp],temp});
                    if(v[temp].size())
                    {
                        int idx=upper_bound(v[temp].begin(),v[temp].end(),j)-v[temp].begin();
                        if(v[temp][idx-1]==j) break;
                    }
                }
                num++;
            }
        }
    }
}
int main()
{
    fastio;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(i==0) st=a;
        else if(i==1) en=a;
        v[a].push_back(b);
    }
    for(int i=0;i<n;i++)
        sort(v[i].begin(),v[i].end());
    go();
    if(d[en]==inf) cout<<-1;
    else cout<<d[en];
}

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