Submission #703986

#	Time	Username	Problem	Language	Result	Execution time	Memory
703986		ToroTN	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1099 ms	83752 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
int n,m,b[30005],p[30005],d[30005],u,cnt,num,cost,block=173;
vector<int> v[30005];
priority_queue<pair<int,int> > pq;
set<int> go[175][175];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<=block;j++)
        {
            go[j][i%j].insert(i);
        }
        d[i]=1e9;
    }
    for(int i=1;i<=m;i++)
    {
        cin >> b[i] >> p[i];
        v[b[i]].pb(p[i]);
    }
    d[b[1]]=0;
    pq.push({0,b[1]});
    while(!pq.empty())
    {
        u=pq.top().Y;
        pq.pop();
        for(int i=1;i<=block;i++)
        {
            if(go[i][u%i].find(u)!=go[i][u%i].end())
            {
                go[i][u%i].erase(u);
            }
        }
        for(auto dis:v[u])
        {
            if(dis>block)
            {
                cnt=0;
                for(int i=u;i>0;i-=dis)
                {
                    if(d[u]+cnt<d[i])
                    {
                        d[i]=d[u]+cnt;
                        pq.push({-d[i],i});
                    }
                    ++cnt;
                }
                cnt=0;
                for(int i=u;i<n;i+=dis)
                {
                    if(d[u]+cnt<d[i])
                    {
                        d[i]=d[u]+cnt;
                        pq.push({-d[i],i});
                    }
                    ++cnt;
                }
            }else
            {
                for(auto it=go[dis][u%dis].begin();it!=go[dis][u%dis].end();it++)
                {
                    num=(*it);
                    cost=abs(u-num)/dis;
                    if(d[u]+cost<d[num])
                    {
                        d[num]=d[u]+cost;
                        pq.push({-d[num],num});
                    }
                }
            }
        }
    }
    if(d[b[2]]==1e9)
    {
        printf("-1\n");
    }else
    {
        printf("%d\n",d[b[2]]);
    }
}

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