oj.uz

Submission #824070

# Submission time Handle Problem Language Result Execution time Memory
824070 2023-08-13T12:49:33 Z lprochniak Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 259 ms 231992 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int max_ans = 5000000;
const int maxN = 30005;
const int maxSqrtN = 200;

int n,m;
int zero,one;
int root;
vector<int> powers[maxN];
vector<ll> q[max_ans];
bool done[maxN][maxSqrtN];
ll Encode(int building,int power){
    assert(power <= maxSqrtN);
    return building + n*power;
}
int dijkstra(){
    int curr_ans = 0;
    int best_ans = -1;
    q[0].pb(Encode(zero,0));
    while(curr_ans < max_ans){
        if(q[curr_ans].empty()){
            curr_ans++;
            continue;
        }

        ll top = q[curr_ans].back();
        q[curr_ans].pop_back();

        int building = top%n;
        int power = top/n;

        if(done[building][power]) continue;
        done[building][power] = true;

        if(building == one){
            if(best_ans == -1){
                best_ans = curr_ans;
            }
            continue;
        }

        //in building
        if(!power){
            for(ll doge:powers[building]){
                //doge in building
                if(doge<=root){
                    q[curr_ans].pb(Encode(building,doge));
                } else{
                    //other building (power>root)
                    for(int dir=-1;dir<2;dir+=2){
                        for(int jumps=1;;jumps++){
                            int pos = building + jumps*dir*doge;
                            if(pos<0 || pos>=n) break;
                            q[curr_ans+jumps].pb(Encode(pos,0));
                        }
                    }
                }
            }
        } else{
            //doge with power <= root
            
            //to building
            q[curr_ans].pb(Encode(building,0));

            //to other doge
            int pos = building + power;
            if(pos<n) q[curr_ans+1].pb(Encode(pos,power));
            pos = building - power;
            if(pos>=0) q[curr_ans+1].pb(Encode(pos,power));
        }
    }
    return best_ans;
}
int main(){
    cin>>n>>m;
    root = (int)sqrt(n);
    for(int i=0;i<m;i++){
        int building,power;
        cin>>building>>power;
        powers[building].pb(power);

        if(i==0) zero = building;
        if(i==1) one = building;
    }
    cout<<dijkstra();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 118356 KB Output is correct
2 Correct 59 ms 118412 KB Output is correct
3 Correct 64 ms 118296 KB Output is correct
4 Correct 62 ms 118372 KB Output is correct
5 Correct 63 ms 118356 KB Output is correct
6 Correct 60 ms 118412 KB Output is correct
7 Correct 63 ms 118412 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 118364 KB Output is correct
2 Correct 65 ms 118396 KB Output is correct
3 Correct 60 ms 118336 KB Output is correct
4 Correct 61 ms 118380 KB Output is correct
5 Correct 61 ms 118308 KB Output is correct
6 Correct 60 ms 118404 KB Output is correct
7 Correct 67 ms 118420 KB Output is correct
8 Correct 61 ms 118408 KB Output is correct
9 Correct 63 ms 118432 KB Output is correct
10 Correct 70 ms 118452 KB Output is correct
11 Correct 66 ms 118508 KB Output is correct
12 Correct 62 ms 118464 KB Output is correct
13 Correct 67 ms 118488 KB Output is correct
14 Correct 64 ms 118452 KB Output is correct
15 Correct 62 ms 118476 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 118412 KB Output is correct
2 Correct 63 ms 118360 KB Output is correct
3 Correct 68 ms 118316 KB Output is correct
4 Correct 62 ms 118352 KB Output is correct
5 Correct 61 ms 118392 KB Output is correct
6 Correct 63 ms 118328 KB Output is correct
7 Correct 60 ms 118404 KB Output is correct
8 Correct 62 ms 118344 KB Output is correct
9 Correct 70 ms 118416 KB Output is correct
10 Correct 64 ms 118424 KB Output is correct
11 Correct 64 ms 118396 KB Output is correct
12 Correct 62 ms 118408 KB Output is correct
13 Correct 63 ms 118408 KB Output is correct
14 Correct 62 ms 118500 KB Output is correct
15 Correct 64 ms 118476 KB Output is correct
16 Correct 62 ms 118412 KB Output is correct
17 Correct 63 ms 118776 KB Output is correct
18 Correct 62 ms 118544 KB Output is correct
19 Correct 62 ms 118476 KB Output is correct
20 Correct 63 ms 118936 KB Output is correct
21 Correct 62 ms 118436 KB Output is correct
22 Correct 62 ms 118392 KB Output is correct
23 Correct 62 ms 118860 KB Output is correct
24 Correct 64 ms 118960 KB Output is correct
25 Correct 62 ms 118980 KB Output is correct
26 Correct 64 ms 118924 KB Output is correct
27 Correct 69 ms 118860 KB Output is correct
28 Correct 64 ms 119468 KB Output is correct
29 Correct 65 ms 120012 KB Output is correct
30 Correct 62 ms 119200 KB Output is correct
31 Correct 64 ms 119456 KB Output is correct
32 Correct 73 ms 119264 KB Output is correct
33 Correct 66 ms 120880 KB Output is correct
34 Correct 69 ms 120912 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 118344 KB Output is correct
2 Correct 63 ms 118324 KB Output is correct
3 Correct 62 ms 118408 KB Output is correct
4 Correct 64 ms 118400 KB Output is correct
5 Correct 65 ms 118420 KB Output is correct
6 Correct 63 ms 118384 KB Output is correct
7 Correct 63 ms 118292 KB Output is correct
8 Correct 62 ms 118344 KB Output is correct
9 Correct 62 ms 118416 KB Output is correct
10 Correct 62 ms 118424 KB Output is correct
11 Correct 65 ms 118416 KB Output is correct
12 Correct 66 ms 118392 KB Output is correct
13 Correct 61 ms 118488 KB Output is correct
14 Correct 63 ms 118424 KB Output is correct
15 Correct 63 ms 118500 KB Output is correct
16 Correct 63 ms 118352 KB Output is correct
17 Correct 63 ms 118728 KB Output is correct
18 Correct 62 ms 118456 KB Output is correct
19 Correct 63 ms 118420 KB Output is correct
20 Correct 62 ms 118912 KB Output is correct
21 Correct 61 ms 118364 KB Output is correct
22 Correct 63 ms 118440 KB Output is correct
23 Correct 64 ms 118792 KB Output is correct
24 Correct 67 ms 118904 KB Output is correct
25 Correct 63 ms 118920 KB Output is correct
26 Correct 69 ms 118844 KB Output is correct
27 Correct 64 ms 118948 KB Output is correct
28 Correct 65 ms 119372 KB Output is correct
29 Correct 64 ms 120056 KB Output is correct
30 Correct 64 ms 119192 KB Output is correct
31 Correct 64 ms 119464 KB Output is correct
32 Correct 64 ms 119164 KB Output is correct
33 Correct 66 ms 120820 KB Output is correct
34 Correct 70 ms 120816 KB Output is correct
35 Correct 73 ms 120140 KB Output is correct
36 Correct 65 ms 118916 KB Output is correct
37 Correct 81 ms 121112 KB Output is correct
38 Correct 77 ms 121028 KB Output is correct
39 Correct 78 ms 121064 KB Output is correct
40 Correct 77 ms 121052 KB Output is correct
41 Correct 76 ms 121028 KB Output is correct
42 Correct 84 ms 119244 KB Output is correct
43 Correct 74 ms 119244 KB Output is correct
44 Correct 75 ms 119536 KB Output is correct
45 Correct 78 ms 123984 KB Output is correct
46 Correct 77 ms 123960 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 118408 KB Output is correct
2 Correct 62 ms 118420 KB Output is correct
3 Correct 67 ms 118536 KB Output is correct
4 Correct 74 ms 118408 KB Output is correct
5 Correct 64 ms 118372 KB Output is correct
6 Correct 62 ms 118336 KB Output is correct
7 Correct 60 ms 118288 KB Output is correct
8 Correct 63 ms 118320 KB Output is correct
9 Correct 64 ms 118312 KB Output is correct
10 Correct 67 ms 118480 KB Output is correct
11 Correct 62 ms 118412 KB Output is correct
12 Correct 63 ms 118372 KB Output is correct
13 Correct 64 ms 118436 KB Output is correct
14 Correct 64 ms 118416 KB Output is correct
15 Correct 65 ms 118384 KB Output is correct
16 Correct 64 ms 118552 KB Output is correct
17 Correct 64 ms 118732 KB Output is correct
18 Correct 62 ms 118356 KB Output is correct
19 Correct 62 ms 118476 KB Output is correct
20 Correct 64 ms 118856 KB Output is correct
21 Correct 64 ms 118348 KB Output is correct
22 Correct 71 ms 118440 KB Output is correct
23 Correct 71 ms 118960 KB Output is correct
24 Correct 66 ms 118992 KB Output is correct
25 Correct 64 ms 118808 KB Output is correct
26 Correct 65 ms 118884 KB Output is correct
27 Correct 63 ms 118860 KB Output is correct
28 Correct 67 ms 119372 KB Output is correct
29 Correct 68 ms 120112 KB Output is correct
30 Correct 66 ms 119124 KB Output is correct
31 Correct 70 ms 119580 KB Output is correct
32 Correct 64 ms 119148 KB Output is correct
33 Correct 66 ms 120848 KB Output is correct
34 Correct 66 ms 120900 KB Output is correct
35 Correct 73 ms 120100 KB Output is correct
36 Correct 66 ms 118892 KB Output is correct
37 Correct 73 ms 121084 KB Output is correct
38 Correct 77 ms 121024 KB Output is correct
39 Correct 77 ms 121064 KB Output is correct
40 Correct 80 ms 121112 KB Output is correct
41 Correct 78 ms 121100 KB Output is correct
42 Correct 72 ms 119144 KB Output is correct
43 Correct 71 ms 119236 KB Output is correct
44 Correct 78 ms 119564 KB Output is correct
45 Correct 79 ms 123932 KB Output is correct
46 Correct 79 ms 123880 KB Output is correct
47 Correct 95 ms 131520 KB Output is correct
48 Correct 74 ms 119140 KB Output is correct
49 Correct 77 ms 119116 KB Output is correct
50 Correct 69 ms 118848 KB Output is correct
51 Correct 88 ms 129756 KB Output is correct
52 Correct 88 ms 130476 KB Output is correct
53 Correct 88 ms 126156 KB Output is correct
54 Correct 65 ms 124648 KB Output is correct
55 Correct 68 ms 125004 KB Output is correct
56 Correct 80 ms 126380 KB Output is correct
57 Correct 90 ms 133140 KB Output is correct
58 Correct 78 ms 126656 KB Output is correct
59 Correct 87 ms 126372 KB Output is correct
60 Correct 82 ms 126352 KB Output is correct
61 Correct 82 ms 126496 KB Output is correct
62 Correct 128 ms 139000 KB Output is correct
63 Correct 103 ms 144852 KB Output is correct
64 Correct 115 ms 149008 KB Output is correct
65 Correct 146 ms 168940 KB Output is correct
66 Correct 259 ms 231992 KB Output is correct
67 Correct 255 ms 231208 KB Output is correct