oj.uz

Submission #823496

# Submission time Handle Problem Language Result Execution time Memory
823496 2023-08-12T15:17:09 Z lprochniak Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 248 ms 262144 KB 
//https://oj.uz/problem/view/APIO15_skyscraper
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
int n,m;
int root;
//position / power
struct E{
    int pos;
    int pow;
    int waga;
};
struct Node{
    int d;
    int pos;
    int pow;
};
class comp{
    public:
        bool operator()(Node A,Node B){
            return A.d<B.d;
        }
};
vector<E> edges[30009][174];
int dis[30009][174];
void build(){
    for(int i=0;i<n;i++){
        for(int j=1;j<=root;j++){
            edges[i][j].pb({i,0,0});
        }
    }
}
void addsmaller(int pos,int pow){
    int pos2 = pos;
    while(pos2+pow<n){
        edges[pos2][pow].pb({pos2+pow,pow,1});
        pos2 += pow;
    }
    pos2 = pos;
    while(pos2-pow>=0){
        edges[pos2][pow].pb({pos2-pow,pow,1});
        pos2 -= pow;
    }
}
void addbigger(int pos,int pow){
    int pos2 = pos;
    int dl = 1;
    while(pos2+pow<n){
        edges[pos][0].pb({pos2+pow,0,dl});
        pos2 += pow;
        dl++;
    }
    pos2 = pos;
    dl = 1;
    while(pos2-pow>=0){
        edges[pos][0].pb({pos2-pow,0,dl});
        pos2 -= pow;
        dl++;
    }
}
void dijkstra(int pocz){
    priority_queue<Node,vector<Node>,comp> q;
    q.push({0,pocz,0});
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        t.d = -t.d;
        if(dis[t.pos][t.pow] != t.d)
            continue;
        for(auto x:edges[t.pos][t.pow]){
            if(t.d + x.waga < dis[x.pos][x.pow]){
                dis[x.pos][x.pow] = t.d + x.waga;
                q.push({-dis[x.pos][x.pow],x.pos,x.pow});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    root = (int)sqrt(n);
    build();
    int zero,one;
    for(int i=0;i<m;i++){
        int pos,pow;
        cin>>pos>>pow;
        if(pow <= root){
            edges[pos][0].pb({pos,pow,0});
            addsmaller(pos,pow);
        } else if(pow<=n){
            addbigger(pos,pow);
        }
        if(i>1) continue;

        if(i == 0){
            zero = pos;
        } else if(i == 1){
            one = pos;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=root;j++){
            dis[i][j] = 1000000000;
        }
    }
    dis[zero][0] = 0;
    dijkstra(zero);
    /*for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            cout<<"pos: "<<i<<" pow: "<<j<<endl;
            for(auto x:edges[i][j]){
                cout<<"pos: "<<x.pos<<" pow: "<<x.pow<<" waga: "<<x.waga<<endl;
            }
        }
    }*/
    if(dis[one][0] == 1000000000){
        cout<<"-1\n";
    } else cout<<dis[one][0]<<endl;
    return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:119:18: warning: 'one' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |     if(dis[one][0] == 1000000000){
      |        ~~~~~~~~~~^
skyscraper.cpp:110:13: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |     dijkstra(zero);
      |     ~~~~~~~~^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 122828 KB Output is correct
2 Correct 52 ms 122888 KB Output is correct
3 Correct 51 ms 122896 KB Output is correct
4 Correct 56 ms 122888 KB Output is correct
5 Correct 53 ms 122824 KB Output is correct
6 Correct 58 ms 122864 KB Output is correct
7 Correct 53 ms 122928 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 122820 KB Output is correct
2 Correct 50 ms 122832 KB Output is correct
3 Correct 58 ms 122824 KB Output is correct
4 Correct 68 ms 122932 KB Output is correct
5 Correct 60 ms 122916 KB Output is correct
6 Correct 54 ms 122828 KB Output is correct
7 Correct 57 ms 122932 KB Output is correct
8 Correct 56 ms 123016 KB Output is correct
9 Correct 55 ms 122908 KB Output is correct
10 Correct 54 ms 122964 KB Output is correct
11 Correct 53 ms 123096 KB Output is correct
12 Correct 67 ms 125484 KB Output is correct
13 Correct 69 ms 125600 KB Output is correct
14 Correct 56 ms 123060 KB Output is correct
15 Correct 55 ms 123096 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 122892 KB Output is correct
2 Correct 54 ms 122812 KB Output is correct
3 Correct 69 ms 122916 KB Output is correct
4 Correct 55 ms 122932 KB Output is correct
5 Correct 53 ms 122928 KB Output is correct
6 Correct 56 ms 122892 KB Output is correct
7 Correct 60 ms 122848 KB Output is correct
8 Correct 66 ms 122888 KB Output is correct
9 Correct 52 ms 122884 KB Output is correct
10 Correct 51 ms 122940 KB Output is correct
11 Correct 53 ms 123192 KB Output is correct
12 Correct 61 ms 125512 KB Output is correct
13 Correct 62 ms 125496 KB Output is correct
14 Correct 53 ms 123128 KB Output is correct
15 Correct 51 ms 123124 KB Output is correct
16 Correct 51 ms 123192 KB Output is correct
17 Correct 54 ms 124308 KB Output is correct
18 Correct 54 ms 126412 KB Output is correct
19 Correct 64 ms 127084 KB Output is correct
20 Correct 142 ms 176996 KB Output is correct
21 Correct 61 ms 123456 KB Output is correct
22 Correct 69 ms 126528 KB Output is correct
23 Correct 57 ms 126032 KB Output is correct
24 Correct 59 ms 126920 KB Output is correct
25 Correct 58 ms 127180 KB Output is correct
26 Correct 133 ms 175568 KB Output is correct
27 Correct 139 ms 175164 KB Output is correct
28 Correct 59 ms 127100 KB Output is correct
29 Correct 73 ms 127156 KB Output is correct
30 Correct 59 ms 127172 KB Output is correct
31 Correct 61 ms 127204 KB Output is correct
32 Correct 59 ms 127416 KB Output is correct
33 Correct 70 ms 128052 KB Output is correct
34 Correct 72 ms 128052 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 122928 KB Output is correct
2 Correct 54 ms 122828 KB Output is correct
3 Correct 53 ms 122932 KB Output is correct
4 Correct 53 ms 122844 KB Output is correct
5 Correct 68 ms 122924 KB Output is correct
6 Correct 53 ms 122908 KB Output is correct
7 Correct 68 ms 122920 KB Output is correct
8 Correct 53 ms 122908 KB Output is correct
9 Correct 51 ms 122960 KB Output is correct
10 Correct 53 ms 123048 KB Output is correct
11 Correct 69 ms 123212 KB Output is correct
12 Correct 53 ms 125492 KB Output is correct
13 Correct 54 ms 125524 KB Output is correct
14 Correct 57 ms 123040 KB Output is correct
15 Correct 54 ms 123072 KB Output is correct
16 Correct 58 ms 123180 KB Output is correct
17 Correct 61 ms 124276 KB Output is correct
18 Correct 59 ms 126372 KB Output is correct
19 Correct 67 ms 126960 KB Output is correct
20 Correct 143 ms 176996 KB Output is correct
21 Correct 56 ms 123388 KB Output is correct
22 Correct 59 ms 126532 KB Output is correct
23 Correct 59 ms 126028 KB Output is correct
24 Correct 60 ms 126856 KB Output is correct
25 Correct 58 ms 127180 KB Output is correct
26 Correct 155 ms 175636 KB Output is correct
27 Correct 135 ms 175260 KB Output is correct
28 Correct 59 ms 127128 KB Output is correct
29 Correct 64 ms 127152 KB Output is correct
30 Correct 77 ms 127148 KB Output is correct
31 Correct 83 ms 127196 KB Output is correct
32 Correct 70 ms 127408 KB Output is correct
33 Correct 70 ms 127936 KB Output is correct
34 Correct 92 ms 127956 KB Output is correct
35 Correct 68 ms 127816 KB Output is correct
36 Correct 58 ms 125028 KB Output is correct
37 Correct 88 ms 131664 KB Output is correct
38 Correct 80 ms 130764 KB Output is correct
39 Correct 80 ms 131148 KB Output is correct
40 Correct 77 ms 130844 KB Output is correct
41 Correct 76 ms 130828 KB Output is correct
42 Runtime error 238 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 122812 KB Output is correct
2 Correct 69 ms 122932 KB Output is correct
3 Correct 53 ms 122832 KB Output is correct
4 Correct 54 ms 122924 KB Output is correct
5 Correct 57 ms 122932 KB Output is correct
6 Correct 63 ms 122916 KB Output is correct
7 Correct 56 ms 122864 KB Output is correct
8 Correct 55 ms 122896 KB Output is correct
9 Correct 53 ms 122944 KB Output is correct
10 Correct 70 ms 122940 KB Output is correct
11 Correct 53 ms 123216 KB Output is correct
12 Correct 72 ms 125556 KB Output is correct
13 Correct 55 ms 125608 KB Output is correct
14 Correct 59 ms 123088 KB Output is correct
15 Correct 59 ms 123132 KB Output is correct
16 Correct 56 ms 123212 KB Output is correct
17 Correct 59 ms 124332 KB Output is correct
18 Correct 62 ms 126396 KB Output is correct
19 Correct 61 ms 127016 KB Output is correct
20 Correct 152 ms 177000 KB Output is correct
21 Correct 58 ms 123376 KB Output is correct
22 Correct 62 ms 126416 KB Output is correct
23 Correct 67 ms 126020 KB Output is correct
24 Correct 64 ms 126856 KB Output is correct
25 Correct 61 ms 127156 KB Output is correct
26 Correct 146 ms 175600 KB Output is correct
27 Correct 140 ms 175204 KB Output is correct
28 Correct 62 ms 127180 KB Output is correct
29 Correct 72 ms 127216 KB Output is correct
30 Correct 64 ms 127076 KB Output is correct
31 Correct 66 ms 127180 KB Output is correct
32 Correct 64 ms 127308 KB Output is correct
33 Correct 70 ms 128016 KB Output is correct
34 Correct 78 ms 128044 KB Output is correct
35 Correct 73 ms 127896 KB Output is correct
36 Correct 63 ms 125016 KB Output is correct
37 Correct 94 ms 131720 KB Output is correct
38 Correct 86 ms 130764 KB Output is correct
39 Correct 85 ms 131264 KB Output is correct
40 Correct 85 ms 130764 KB Output is correct
41 Correct 85 ms 130844 KB Output is correct
42 Runtime error 248 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -