Submission #16649

#	Time	Username	Problem	Language	Result	Execution time	Memory
16649		khsoo01	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	100 / 100	104 ms	153016 KiB

skyscraper

#include<cstdio>
#include<vector>
#include<queue>
#define INF 0x7fffffff
#define f first
#define s second
using namespace std;
vector<int>cg[50005];
priority_queue<pair<int,int> >pq;
int dist[30005],ed[30005][2];
int n,m,a,b,cur,val,tmp;
bool chk[30005][5005];

int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++) {
        scanf("%d%d",&ed[i][0],&ed[i][1]);
        if(ed[i][1]>5000 || !chk[ed[i][0]][ed[i][1]])
            cg[ed[i][0]].push_back(ed[i][1]);
        if(ed[i][1]<=5000) chk[ed[i][0]][ed[i][1]]=1;
    }
    for(i=0;i<n;i++) dist[i]=INF;
    dist[ed[0][0]]=0;
    pq.push({0,ed[0][0]});
    while(!pq.empty()) {
        val=-pq.top().first;
        cur=pq.top().second;
        pq.pop();
        if(cur==ed[1][0])break;
        if(dist[cur]!=val) continue;
        for(i=0;i<cg[cur].size();i++) {
            tmp=cg[cur][i];
            for(j=cur+tmp;j<n;j+=tmp) {
                if(dist[j]>dist[cur]+(j-cur)/tmp) {
                    dist[j]=dist[cur]+(j-cur)/tmp;
                    pq.push({-dist[j],j});
                }
                if(tmp<=5000 && chk[j][tmp])break;
            }
            for(j=cur-tmp;j>=0;j-=tmp) {
                if(dist[j]>dist[cur]+(cur-j)/tmp) {
                    dist[j]=dist[cur]+(cur-j)/tmp;
                    pq.push({-dist[j],j});
                }
                if(tmp<=5000 && chk[j][tmp])break;
            }
        }
    }
    printf("%d",dist[ed[1][0]]==INF?-1:dist[ed[1][0]]);
}

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