oj.uz

Submission #823582

# Submission time Handle Problem Language Result Execution time Memory
823582 2023-08-12T19:20:47 Z lprochniak Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 382 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;
        }
};
map<pair<int,int>,bool> odw;
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;
		  pii para = {pos,pow};
        if(odw[{pos,pow}]) continue;
            else odw[{pos,pow}] = 1;
        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;
            s += edges[i][j].size();
            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:91:9: warning: variable 'para' set but not used [-Wunused-but-set-variable]
   91 |     pii para = {pos,pow};
      |         ^~~~
skyscraper.cpp:125:18: warning: 'one' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |     if(dis[one][0] == 1000000000){
      |        ~~~~~~~~~~^
skyscraper.cpp:114:13: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     dijkstra(zero);
      |     ~~~~~~~~^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 122924 KB Output is correct
2 Correct 50 ms 122900 KB Output is correct
3 Correct 51 ms 122932 KB Output is correct
4 Correct 52 ms 122932 KB Output is correct
5 Correct 52 ms 122812 KB Output is correct
6 Correct 50 ms 122812 KB Output is correct
7 Correct 50 ms 122828 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 122884 KB Output is correct
2 Correct 51 ms 122932 KB Output is correct
3 Correct 51 ms 122828 KB Output is correct
4 Correct 51 ms 122872 KB Output is correct
5 Correct 51 ms 122820 KB Output is correct
6 Correct 50 ms 122940 KB Output is correct
7 Correct 51 ms 122904 KB Output is correct
8 Correct 51 ms 122872 KB Output is correct
9 Correct 59 ms 122884 KB Output is correct
10 Correct 51 ms 123044 KB Output is correct
11 Correct 53 ms 123308 KB Output is correct
12 Correct 52 ms 122992 KB Output is correct
13 Correct 52 ms 123160 KB Output is correct
14 Correct 53 ms 123152 KB Output is correct
15 Correct 52 ms 123176 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 122824 KB Output is correct
2 Correct 52 ms 122916 KB Output is correct
3 Correct 51 ms 122932 KB Output is correct
4 Correct 51 ms 122880 KB Output is correct
5 Correct 50 ms 122828 KB Output is correct
6 Correct 51 ms 122932 KB Output is correct
7 Correct 52 ms 122864 KB Output is correct
8 Correct 50 ms 122944 KB Output is correct
9 Correct 50 ms 122928 KB Output is correct
10 Correct 51 ms 122996 KB Output is correct
11 Correct 52 ms 123316 KB Output is correct
12 Correct 52 ms 122992 KB Output is correct
13 Correct 52 ms 123212 KB Output is correct
14 Correct 51 ms 123216 KB Output is correct
15 Correct 52 ms 123184 KB Output is correct
16 Correct 51 ms 123192 KB Output is correct
17 Correct 55 ms 124468 KB Output is correct
18 Correct 62 ms 126468 KB Output is correct
19 Correct 56 ms 127092 KB Output is correct
20 Correct 136 ms 177336 KB Output is correct
21 Correct 51 ms 123468 KB Output is correct
22 Correct 60 ms 126696 KB Output is correct
23 Correct 55 ms 126056 KB Output is correct
24 Correct 57 ms 127040 KB Output is correct
25 Correct 57 ms 127308 KB Output is correct
26 Correct 56 ms 127308 KB Output is correct
27 Correct 58 ms 127080 KB Output is correct
28 Correct 112 ms 127320 KB Output is correct
29 Correct 64 ms 127180 KB Output is correct
30 Correct 59 ms 127156 KB Output is correct
31 Correct 62 ms 127200 KB Output is correct
32 Correct 60 ms 127456 KB Output is correct
33 Correct 70 ms 128076 KB Output is correct
34 Correct 69 ms 128020 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 122928 KB Output is correct
2 Correct 52 ms 122888 KB Output is correct
3 Correct 52 ms 122828 KB Output is correct
4 Correct 51 ms 122932 KB Output is correct
5 Correct 51 ms 122844 KB Output is correct
6 Correct 53 ms 122844 KB Output is correct
7 Correct 52 ms 122912 KB Output is correct
8 Correct 53 ms 122844 KB Output is correct
9 Correct 52 ms 122980 KB Output is correct
10 Correct 51 ms 123056 KB Output is correct
11 Correct 54 ms 123208 KB Output is correct
12 Correct 58 ms 122972 KB Output is correct
13 Correct 52 ms 123132 KB Output is correct
14 Correct 54 ms 123212 KB Output is correct
15 Correct 56 ms 123304 KB Output is correct
16 Correct 52 ms 123208 KB Output is correct
17 Correct 54 ms 124484 KB Output is correct
18 Correct 56 ms 126400 KB Output is correct
19 Correct 57 ms 127128 KB Output is correct
20 Correct 153 ms 177456 KB Output is correct
21 Correct 51 ms 123444 KB Output is correct
22 Correct 57 ms 126572 KB Output is correct
23 Correct 55 ms 126060 KB Output is correct
24 Correct 57 ms 126980 KB Output is correct
25 Correct 57 ms 127344 KB Output is correct
26 Correct 57 ms 127268 KB Output is correct
27 Correct 57 ms 127024 KB Output is correct
28 Correct 60 ms 127268 KB Output is correct
29 Correct 63 ms 127248 KB Output is correct
30 Correct 63 ms 127196 KB Output is correct
31 Correct 60 ms 127196 KB Output is correct
32 Correct 59 ms 127420 KB Output is correct
33 Correct 71 ms 128064 KB Output is correct
34 Correct 68 ms 128120 KB Output is correct
35 Correct 77 ms 129484 KB Output is correct
36 Correct 57 ms 125336 KB Output is correct
37 Correct 87 ms 132748 KB Output is correct
38 Correct 89 ms 132600 KB Output is correct
39 Correct 101 ms 133068 KB Output is correct
40 Correct 92 ms 132632 KB Output is correct
41 Correct 87 ms 132676 KB Output is correct
42 Correct 61 ms 127436 KB Output is correct
43 Correct 58 ms 127264 KB Output is correct
44 Correct 136 ms 177356 KB Output is correct
45 Correct 90 ms 134724 KB Output is correct
46 Correct 104 ms 134600 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 122848 KB Output is correct
2 Correct 54 ms 122896 KB Output is correct
3 Correct 51 ms 122932 KB Output is correct
4 Correct 51 ms 122868 KB Output is correct
5 Correct 50 ms 122828 KB Output is correct
6 Correct 51 ms 122936 KB Output is correct
7 Correct 52 ms 122940 KB Output is correct
8 Correct 57 ms 122876 KB Output is correct
9 Correct 52 ms 122960 KB Output is correct
10 Correct 51 ms 123080 KB Output is correct
11 Correct 53 ms 123276 KB Output is correct
12 Correct 52 ms 123040 KB Output is correct
13 Correct 53 ms 123208 KB Output is correct
14 Correct 53 ms 123208 KB Output is correct
15 Correct 52 ms 123140 KB Output is correct
16 Correct 52 ms 123280 KB Output is correct
17 Correct 60 ms 124504 KB Output is correct
18 Correct 55 ms 126392 KB Output is correct
19 Correct 56 ms 127100 KB Output is correct
20 Correct 141 ms 177392 KB Output is correct
21 Correct 52 ms 123452 KB Output is correct
22 Correct 62 ms 126480 KB Output is correct
23 Correct 57 ms 126080 KB Output is correct
24 Correct 58 ms 127044 KB Output is correct
25 Correct 57 ms 127224 KB Output is correct
26 Correct 58 ms 127440 KB Output is correct
27 Correct 62 ms 127068 KB Output is correct
28 Correct 60 ms 127312 KB Output is correct
29 Correct 63 ms 127148 KB Output is correct
30 Correct 58 ms 127180 KB Output is correct
31 Correct 61 ms 127236 KB Output is correct
32 Correct 58 ms 127412 KB Output is correct
33 Correct 81 ms 128076 KB Output is correct
34 Correct 69 ms 128076 KB Output is correct
35 Correct 77 ms 129468 KB Output is correct
36 Correct 57 ms 125260 KB Output is correct
37 Correct 93 ms 132812 KB Output is correct
38 Correct 91 ms 132512 KB Output is correct
39 Correct 91 ms 133032 KB Output is correct
40 Correct 90 ms 132692 KB Output is correct
41 Correct 89 ms 132556 KB Output is correct
42 Correct 64 ms 127472 KB Output is correct
43 Correct 60 ms 127220 KB Output is correct
44 Correct 142 ms 177372 KB Output is correct
45 Correct 95 ms 134648 KB Output is correct
46 Correct 90 ms 134608 KB Output is correct
47 Correct 382 ms 190540 KB Output is correct
48 Correct 233 ms 252732 KB Output is correct
49 Runtime error 189 ms 262144 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -