oj.uz

Submission #14568

# Submission time Handle Problem Language Result Execution time Memory
14568 2015-05-20T06:14:14 Z dohyun0324 Jakarta Skyscrapers (APIO15_skyscraper) C++
10 / 100
 1 ms 89364 KB 
#include<stdio.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
bool ch[30010][175];
vector<int>con[30010];
typedef pair<int,int> ppair;
struct data{
    int val,x,y,c;
    bool operator<(const data&r)const{
        return val>r.val;
    }
}b;
data q[30010*175];
int sw,n,m,root,s,pos,f=-1,r=0;
struct data2{
    int x,p;
}a[30010];
int main()
{
    int sw2,i,j,val,x,y,c;
    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[0]=b;
    while(f<r)
    {
        sw2=0;
        while(f<r)
        {
            f++;
            if(q[f].y<=root)
            {
                if(ch[q[f].x][q[f].y]) continue;
                else{sw2=1; break;}
            }
            x=q[f].x; val=q[f].val; y=q[f].y; c=q[f].c;
            if(x==a[1].x){printf("%d",val); return 0;}
            if(ch[x][0]==0)
            {
                for(i=0;i<con[x].size();i++){
                    b.val=val; b.x=x; b.y=con[x][i]; b.c=0;
                    q[++r]=b;
                }
            }
            if(c==1 || c==0){
                for(i=x+y;i<n;i+=y){
                    if(ch[i][0]) continue;
                    b.val=val+(i-x)/y; b.x=i; b.y=y; b.c=1; q[++r]=b; break;
                }
            }
            if(c==2 || c==0){
                for(i=x-y;i>=0;i-=y){
                    if(ch[i][0]) continue;
                    b.val=val+(x-i)/y; b.x=i; b.y=y; b.c=2; q[++r]=b; break;
                }
            }
            ch[x][0]=1;
        }
        if(!sw2){sw=1; break;}
        val=q[f].val; x=q[f].x; y=q[f].y; ch[x][y]=1;
        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]; b.c=0;
                q[++r]=b;
            }
        }
        ch[x][0]=1;
        if(x+y<n) b.val=val+1, b.x=x+y, b.y=y, b.c=0, q[++r]=b;
        if(x-y>=0) b.val=val+1, b.x=x-y, b.y=y, b.c=0, q[++r]=b;
    }
    if(sw) printf("-1");
    else printf("%d",val);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 89364 KB Output is correct
2 Correct 0 ms 89364 KB Output is correct
3 Correct 0 ms 89364 KB Output is correct
4 Correct 0 ms 89364 KB Output is correct
5 Correct 0 ms 89364 KB Output is correct
6 Correct 0 ms 89364 KB Output is correct
7 Correct 0 ms 89364 KB Output is correct

Subtask #2
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 89364 KB Output is correct
2 Correct 0 ms 89364 KB Output is correct
3 Correct 0 ms 89364 KB Output is correct
4 Correct 0 ms 89364 KB Output is correct
5 Correct 0 ms 89364 KB Output is correct
6 Correct 0 ms 89364 KB Output is correct
7 Correct 0 ms 89364 KB Output is correct
8 Correct 0 ms 89364 KB Output is correct
9 Incorrect 0 ms 89364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 89364 KB Output is correct
2 Correct 0 ms 89364 KB Output is correct
3 Correct 0 ms 89364 KB Output is correct
4 Correct 0 ms 89364 KB Output is correct
5 Correct 0 ms 89364 KB Output is correct
6 Correct 0 ms 89364 KB Output is correct
7 Correct 0 ms 89364 KB Output is correct
8 Correct 0 ms 89364 KB Output is correct
9 Incorrect 0 ms 89364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 89364 KB Output is correct
2 Correct 0 ms 89364 KB Output is correct
3 Correct 0 ms 89364 KB Output is correct
4 Correct 0 ms 89364 KB Output is correct
5 Correct 0 ms 89364 KB Output is correct
6 Correct 0 ms 89364 KB Output is correct
7 Correct 0 ms 89364 KB Output is correct
8 Correct 0 ms 89364 KB Output is correct
9 Incorrect 0 ms 89364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 89364 KB Output is correct
2 Correct 0 ms 89364 KB Output is correct
3 Correct 0 ms 89364 KB Output is correct
4 Correct 0 ms 89364 KB Output is correct
5 Correct 0 ms 89364 KB Output is correct
6 Correct 0 ms 89364 KB Output is correct
7 Correct 0 ms 89364 KB Output is correct
8 Correct 0 ms 89364 KB Output is correct
9 Incorrect 1 ms 89364 KB Output isn't correct
10 Halted 0 ms 0 KB -