Submission #14564

#	Time	Username	Problem	Language	Result	Execution time	Memory
14564		dohyun0324	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	57 / 100	1000 ms	45488 KiB

skyscraper

#include<stdio.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
bool ch[30010][200];
vector<int>con[30010];
typedef pair<int,int> ppair;
struct data{
    int val,x,y;
    bool operator<(const data&r)const{
        return val>r.val;
    }
}b;
priority_queue<data>q;
int sw,n,m,root,s,pos;
struct data2{
    int x,p;
}a[30010];
int main()
{
    int i,j,val,x,y;
    scanf("%d %d",&n,&m);
    root=sqrt(n);
    for(i=0;i<m;i++){scanf("%d %d",&a[i].x,&a[i].p); con[a[i].x].push_back(a[i].p);}
    b.val=0, b.x=a[0].x, b.y=a[0].p, q.push(b);
    while(1){
        while(q.size())
        {
            if(q.top().y<=root)
            {
                if(ch[q.top().x][q.top().y]){q.pop(); continue;}
                else break;
            }
            x=q.top().x; val=q.top().val; y=q.top().y;
            if(x==a[1].x){printf("%d",val); return 0;}
            q.pop();
            for(i=x+y;i<n;i+=y){
                if(ch[i][0]) continue;
                b.val=val+(i-x)/y; b.x=i; b.y=n; q.push(b);
            }
            for(i=x-y;i>=0;i-=y){
                if(ch[i][0]) continue;
                b.val=val+(x-i)/y; b.x=i; b.y=n; q.push(b);
            }
            if(ch[x][0]) continue;
            for(i=0;i<con[x].size();i++){
                b.val=val; b.x=x; b.y=con[x][i];
                if(b.y<=root && ch[b.x][b.y]) continue;
                q.push(b);
            }
            ch[x][0]=1;
        }
        if(q.size()==0){sw=1; break;}
        val=q.top().val; x=q.top().x; y=q.top().y; ch[x][y]=1; q.pop();
        if(x==a[1].x) break;
        if(ch[x][0]==0)
        {
            for(i=0;i<con[x].size();i++){
                b.val=val; b.x=x; b.y=con[x][i];
                if(b.y<=root && ch[b.x][b.y]) continue;
                q.push(b);
            }
        }
        ch[x][0]=1;
        if(x+y<n) b.val=val+1, b.x=x+y, b.y=y, q.push(b);
        if(x-y>=0) b.val=val+1, b.x=x-y, b.y=y, q.push(b);
    }
    if(sw) printf("-1");
    else printf("%d",val);
    return 0;
}

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