oj.uz

Submission #14545

# Submission time Handle Problem Language Result Execution time Memory
14545 2015-05-19T14:40:27 Z dohyun0324 Jakarta Skyscrapers (APIO15_skyscraper) C++
22 / 100
 17 ms 50052 KB 
#include<stdio.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
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,d[30010][200],s,pos,ch[30010][200];
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);}
    d[a[0].x][a[0].p]=0;
    b.val=0, b.x=a[0].x, b.y=a[0].p, q.push(b);
    while(1)
    {
        while(q.size() && ch[q.top().x][q.top().y]) q.pop();
        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;
        for(i=0;i<con[x].size();i++){
            b.val=val; b.x=x; b.y=con[x][i];
            q.push(b);
        }
        if(y<=root){
            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);
        }
        else{
            for(i=x+y;i<n;i+=y){
                b.val=val+(i-x)/y; b.x=i; b.y=y; q.push(b);
            }
            for(i=x-y;i>=0;i-=y){
                b.val=val+(x-i)/y; b.x=i; b.y=y; q.push(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 1 ms 49432 KB Output is correct
2 Correct 0 ms 49432 KB Output is correct
3 Correct 0 ms 49432 KB Output is correct
4 Correct 1 ms 49432 KB Output is correct
5 Correct 0 ms 49432 KB Output is correct
6 Correct 0 ms 49432 KB Output is correct
7 Correct 0 ms 49432 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49432 KB Output is correct
2 Correct 0 ms 49432 KB Output is correct
3 Correct 0 ms 49432 KB Output is correct
4 Correct 0 ms 49432 KB Output is correct
5 Correct 0 ms 49432 KB Output is correct
6 Correct 0 ms 49432 KB Output is correct
7 Correct 0 ms 49432 KB Output is correct
8 Correct 0 ms 49432 KB Output is correct
9 Correct 1 ms 49432 KB Output is correct
10 Correct 0 ms 49432 KB Output is correct
11 Correct 0 ms 49432 KB Output is correct
12 Correct 0 ms 49432 KB Output is correct
13 Correct 0 ms 49432 KB Output is correct
14 Correct 17 ms 49832 KB Output is correct
15 Correct 7 ms 49832 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49432 KB Output is correct
2 Correct 0 ms 49432 KB Output is correct
3 Correct 0 ms 49432 KB Output is correct
4 Correct 0 ms 49432 KB Output is correct
5 Correct 0 ms 49432 KB Output is correct
6 Correct 0 ms 49432 KB Output is correct
7 Correct 0 ms 49432 KB Output is correct
8 Correct 0 ms 49432 KB Output is correct
9 Correct 0 ms 49432 KB Output is correct
10 Correct 0 ms 49432 KB Output is correct
11 Correct 0 ms 49432 KB Output is correct
12 Correct 0 ms 49432 KB Output is correct
13 Correct 0 ms 49432 KB Output is correct
14 Correct 17 ms 49832 KB Output is correct
15 Correct 11 ms 49832 KB Output is correct
16 Correct 0 ms 49432 KB Output is correct
17 Correct 3 ms 49840 KB Output is correct
18 Correct 0 ms 49432 KB Output is correct
19 Correct 0 ms 49432 KB Output is correct
20 Correct 0 ms 49432 KB Output is correct
21 Correct 0 ms 49432 KB Output is correct
22 Correct 1 ms 49432 KB Output is correct
23 Correct 7 ms 49648 KB Output is correct
24 Correct 4 ms 50052 KB Output is correct
25 Correct 0 ms 49432 KB Output is correct
26 Correct 0 ms 49432 KB Output is correct
27 Correct 4 ms 49432 KB Output is correct
28 Incorrect 14 ms 49432 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49432 KB Output is correct
2 Correct 0 ms 49432 KB Output is correct
3 Correct 0 ms 49432 KB Output is correct
4 Correct 0 ms 49432 KB Output is correct
5 Correct 0 ms 49432 KB Output is correct
6 Correct 0 ms 49432 KB Output is correct
7 Correct 0 ms 49432 KB Output is correct
8 Correct 0 ms 49432 KB Output is correct
9 Correct 0 ms 49432 KB Output is correct
10 Correct 0 ms 49432 KB Output is correct
11 Correct 0 ms 49432 KB Output is correct
12 Correct 0 ms 49432 KB Output is correct
13 Correct 0 ms 49432 KB Output is correct
14 Correct 17 ms 49832 KB Output is correct
15 Correct 12 ms 49832 KB Output is correct
16 Correct 0 ms 49432 KB Output is correct
17 Correct 0 ms 49840 KB Output is correct
18 Correct 0 ms 49432 KB Output is correct
19 Correct 0 ms 49432 KB Output is correct
20 Correct 0 ms 49432 KB Output is correct
21 Correct 0 ms 49432 KB Output is correct
22 Correct 0 ms 49432 KB Output is correct
23 Correct 6 ms 49648 KB Output is correct
24 Correct 4 ms 50052 KB Output is correct
25 Correct 0 ms 49432 KB Output is correct
26 Correct 0 ms 49432 KB Output is correct
27 Correct 4 ms 49432 KB Output is correct
28 Incorrect 14 ms 49432 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 49432 KB Output is correct
2 Correct 0 ms 49432 KB Output is correct
3 Correct 0 ms 49432 KB Output is correct
4 Correct 0 ms 49432 KB Output is correct
5 Correct 0 ms 49432 KB Output is correct
6 Correct 0 ms 49432 KB Output is correct
7 Correct 0 ms 49432 KB Output is correct
8 Correct 0 ms 49432 KB Output is correct
9 Correct 1 ms 49432 KB Output is correct
10 Correct 1 ms 49432 KB Output is correct
11 Correct 2 ms 49432 KB Output is correct
12 Correct 0 ms 49432 KB Output is correct
13 Correct 0 ms 49432 KB Output is correct
14 Correct 17 ms 49832 KB Output is correct
15 Correct 8 ms 49832 KB Output is correct
16 Correct 0 ms 49432 KB Output is correct
17 Correct 3 ms 49840 KB Output is correct
18 Correct 0 ms 49432 KB Output is correct
19 Correct 0 ms 49432 KB Output is correct
20 Correct 2 ms 49432 KB Output is correct
21 Correct 0 ms 49432 KB Output is correct
22 Correct 0 ms 49432 KB Output is correct
23 Correct 7 ms 49648 KB Output is correct
24 Correct 6 ms 50052 KB Output is correct
25 Correct 0 ms 49432 KB Output is correct
26 Correct 0 ms 49432 KB Output is correct
27 Correct 0 ms 49432 KB Output is correct
28 Incorrect 11 ms 49432 KB Output isn't correct
29 Halted 0 ms 0 KB -