Submission #847207

#	Time	Username	Problem	Language	Result	Execution time	Memory
847207		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	461 ms	23764 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second

const int ar=3e4+5;
const ll mod=1e9+7;

int n,m;
int sqr;
int b[ar];
int p[ar];
int dp[ar][174];
vector<int> ad[ar];
struct seg
{
    int dis,i,p;
};
bool operator>(seg a,seg b)
{
    return a.dis>b.dis;
}
priority_queue<seg,vector<seg>, greater<seg> > pq;
int ans=1e9;
void dijkstra()
{
    memset(dp,0x3f,sizeof dp);
    pq.push({0,b[0],0});
    dp[b[0]][0]=0;
    while(pq.size())
    {
        seg top=pq.top();
        pq.pop();
        int dis=top.dis;
        int i=top.i;
        int pk=top.p;
        if (dp[i][pk]<dis) continue;
        if (i==b[1]) ans=min(ans,dis);
        if (pk==0)
        {
            for (auto x:ad[i])
            {
                if (p[x]<=sqr)
                {
                    if (dp[i][p[x]]>dis)
                    {
                        dp[i][p[x]]=dis;
                        pq.push({dis,i,p[x]});
                    }
                }
                else
                {
                    int cnt=0;
                    for (int j=i;j<n;j+=p[x])
                    {
                        if (dp[j][0]>dis+cnt)
                        {
                            dp[j][0]=dis+cnt;
                            pq.push({dp[j][0],j,0});
                        }
                        cnt++;
                    }
                    cnt=0;
                    for (int j=i;j>=0;j-=p[x])
                    {
                        if (dp[j][0]>dis+cnt)
                        {
                            dp[j][0]=dis+cnt;
                            pq.push({dp[j][0],j,0});
                        }
                        cnt++;
                    }
                }
            }
        }
        else
        {
            if (i+pk<n && dp[i+pk][pk]>dis+1)
            {
                dp[i+pk][pk]=dis+1;
                pq.push({dp[i+pk][pk],i+pk,pk});
            }
            if (i-pk>=0 && dp[i-pk][pk]>dis+1)
            {
                dp[i-pk][pk]=dis+1;
                pq.push({dp[i-pk][pk],i-pk,pk});
            }
            if (dp[i][0]>dis)
            {
                dp[i][0]=dis;
                pq.push({dp[i][0],i,0});
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=0;i<m;i++)
    {
        cin>>b[i]>>p[i];
        ad[b[i]].push_back(i);
    }
    sqr=sqrt(n);
    dijkstra();
    if (ans==1e9) ans=-1;
    cout<<ans;
///
}

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