Submission #703980

#	Time	Username	Problem	Language	Result	Execution time	Memory
703980		ToroTN	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	2516 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
int n,m,b,p,d[30005],u,cnt,num,cost;
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<=173;j++)
        {
            go[j][i%j].insert(i);
        }
        d[i]=1e9;
    }
    while(m--)
    {
        cin >> b >> p;
        v[b].pb(p);
    }
    d[0]=0;
    pq.push({0,0});
    while(!pq.empty())
    {
        u=pq.top().Y;
        pq.pop();
        for(int i=1;i<=173;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>173)
            {
                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[1]==1e9)
    {
        printf("-1\n");
    }else
    {
        printf("%d\n",d[1]);
    }
}

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