제출 #1155380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155380		vivkostov	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	2700 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.st>st;
    }
};
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;
}
void dijkstra()
{
    cell w,nb;
    w.st=a[1].st;
    w.to=a[1].to;
    w.ind=1;
    w.tim=0;
    q.push(w);
    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;
        //cout<<w.ind<<" "<<w.st<<" "<<w.to<<endl;
        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<<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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43