Submission #1155386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155386		vivkostov	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	29 ms	6852 KiB

skyscraper

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int to,st,tim,ind;
    bool operator<(const cell&a)const
    {
        return a.tim<tim;
    }
};
int n,m,used[505][505],ti[100005],dogtim[100005];
cell a[100005];
vector<cell>v[100005];
priority_queue<cell>q;
void prec()
{
    for(int i=1;i<=n;i++)
    {
        ti[i]=1e9;
    }
    for(int j=1;j<=m;j++)
    {
        dogtim[j]=1e9;
    }
    dogtim[1]=0;
    ti[a[1].to]=0;
}
void dijkstra()
{
    cell w,nb;
    int start=a[1].to;
    for(int i=0;i<v[start].size();i++)
    {
        nb.st=v[start][i].st;
        nb.to=v[start][i].to;
        nb.tim=ti[start];
        nb.ind=v[start][i].ind;
        q.push(nb);
    }
    int izm=0;
    while(!q.empty())
    {
        w=q.top();
        q.pop();
        if(w.ind==2)
        {
            cout<<w.tim<<endl;
            exit(0);
        }
        if(dogtim[w.ind]<w.tim)continue;
        if(w.st<300)
        {
            if(used[w.st][w.to%w.st])continue;
            used[w.st][w.to%w.st]=1;
        }
        izm=0;
        for(int i=w.to+w.st;i<=n;i+=w.st)
        {
            izm++;
            if(ti[i]<=w.tim+izm)continue;
            ti[i]=w.tim+izm;
            //cout<<w.ind<<" "<<i<<" "<<w.to<<" "<<w.st<<endl;
            for(int j=0;j<v[i].size();j++)
            {
                nb.st=v[i][j].st;
                nb.to=i;
                nb.tim=ti[i];
                nb.ind=v[i][j].ind;
                q.push(nb);
                dogtim[v[i][j].ind]=ti[i];
            }
        }
        izm=0;
        for(int i=w.to-w.st;i>=1;i-=w.st)
        {
            izm++;
            if(ti[i]<=w.tim+izm)continue;
            ti[i]=w.tim+izm;
            for(int j=0;j<v[i].size();j++)
            {
                nb.st=v[i][j].st;
                nb.to=i;
                nb.tim=ti[i];
                nb.ind=v[i][j].ind;
                q.push(nb);
                dogtim[v[i][j].ind]=ti[i];
            }
        }
    }
}
void read()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].to>>a[i].st;
        a[i].to++;
        a[i].ind=i;
        v[a[i].to].push_back(a[i]);
    }
    cout<<endl;
    prec();
    dijkstra();
    cout<<-1<<endl;
}
int main()
{
    speed();
    read();
    return 0;
}

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