Submission #17606

#	Time	Username	Problem	Language	Result	Execution time	Memory
17606		dohyun0324	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	100 / 100	104 ms	29408 KiB

skyscraper

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
typedef pair<int,int> ppair;
vector<int>v[30010];
priority_queue<ppair, vector<ppair>, greater<ppair> >q;
int ch[30010],val,x,y,pos,n,m,t,en,arr[200][30010],d[30010];
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    t=sqrt(n);
    for(i=1;i<=m;i++){
        scanf("%d %d",&x,&y); v[++x].push_back(y);
        if(i==1) pos=x;
        if(i==2) en=x;
    }
    for(i=1;i<=n;i++) d[i]=1e9; d[pos]=0; ch[pos]=1;
    while(1)
    {
        for(i=0;i<v[pos].size();i++)
        {
            val=v[pos][i];
            if(val<=t)
            {
                if(arr[val][pos]) continue;
                arr[val][pos]=1;
                for(j=pos+val;j<=n;j+=val){
                    if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]+(j-pos)/val; q.push(make_pair(d[pos]+(j-pos)/val,j));}
                    arr[val][j]=1;
                }
                for(j=pos-val;j>=1;j-=val){
                    if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]-(j-pos)/val; q.push(make_pair(d[pos]-(j-pos)/val,j));}
                    arr[val][j]=1;
                }
            }
            else
            {
                for(j=pos+val;j<=n;j+=val){
                    if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]+(j-pos)/val; q.push(make_pair(d[pos]+(j-pos)/val,j));}
                }
                for(j=pos-val;j>=1;j-=val){
                    if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]-(j-pos)/val; q.push(make_pair(d[pos]-(j-pos)/val,j));}
                }
            }
        }
        while(q.size() && ch[q.top().second]) q.pop();
        if(q.size()==0) break;
        pos=q.top().second; d[pos]=q.top().first; ch[pos]=1;
        if(q.top().second==en) break;
    }
    if(d[en]==1e9) printf("-1");
    else printf("%d",d[en]);
    return 0;
}

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