oj.uz

Submission #553573

# Submission time Handle Problem Language Result Execution time Memory
553573 2022-04-26T09:32:41 Z Jarif_Rahman Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 1287 ms 37904 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int K = 21;
const int inf = 1e9;

int n;
vector<int> h;
vector<int> jump[2];
vector<int> anc[2][K];

template<int k>
int get_anc(int nd, int h){
    for(int i = 0; i < K; i++){
        if(h%2 == 1) nd = anc[k][i][nd];
        h/=2;
    }
    return nd;
}

template<int k>
int binlift(int nd, int l){
    if(h[nd] == l) return 0;
    if(h[nd] > l) return -inf;
    for(int i = K-1; i >= 0; i--) if(h[anc[k][i][nd]] < l)
        return binlift<k>(anc[k][i][nd], l)+(1<<i);
    if(h[anc[k][0][nd]] == l) return 1;
    return 0;
}

void init(int N, vector<int> H){
    for(int &x: H) x--;
    n = N, h = H;
    h.pb(n);
    fill(jump, jump+2, vector<int>(n, n));
    fill(anc[0], anc[0]+K, vector<int>(n+1, n));
    fill(anc[1], anc[1]+K, vector<int>(n+1, n));

    stack<int> st;
    for(int i = n-1; i >= 0; i--){
        while(!st.empty() && h[i] > h[st.top()]){
            jump[0][st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();

    for(int i = 0; i < n; i++){
        while(!st.empty() && h[i] > h[st.top()]){
            jump[1][st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();

    for(int i = 0; i < n; i++){
        anc[0][0][i] = h[jump[0][i]] < h[jump[1][i]] ? jump[0][i] : jump[1][i];
        anc[1][0][i] = h[jump[0][i]] > h[jump[1][i]] ? jump[0][i] : jump[1][i];
        if(anc[1][0][i] == n) anc[1][0][i] = anc[0][0][i];
    }

    for(int p = 1; p < K; p++) for(int i = 0; i <= n; i++)
        anc[0][p][i] = anc[0][p-1][anc[0][p-1][i]],
        anc[1][p][i] = anc[1][p-1][anc[1][p-1][i]];
}

int minimum_jumps(int A, int B, int C, int D){
    int ans = binlift<1>(A, h[C]);
    if(ans < 0) return -1;
    int nd = get_anc<1>(A, ans);
    int x = binlift<0>(nd, h[C]);
    if(x < 0) return -1;
    nd = get_anc<0>(nd, x);
    ans+=x;
    if(nd == C) return ans;
    return -1;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 139 ms 30120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 209 ms 17384 KB Output is correct
5 Correct 881 ms 37868 KB Output is correct
6 Correct 615 ms 6476 KB Output is correct
7 Correct 781 ms 37796 KB Output is correct
8 Correct 537 ms 13196 KB Output is correct
9 Correct 853 ms 37896 KB Output is correct
10 Correct 1274 ms 37848 KB Output is correct
11 Correct 1287 ms 37816 KB Output is correct
12 Correct 1110 ms 37788 KB Output is correct
13 Correct 977 ms 37816 KB Output is correct
14 Correct 1080 ms 37760 KB Output is correct
15 Correct 842 ms 37796 KB Output is correct
16 Correct 787 ms 37816 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 208 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 208 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 11 ms 680 KB Output is correct
28 Correct 22 ms 592 KB Output is correct
29 Correct 20 ms 592 KB Output is correct
30 Correct 16 ms 592 KB Output is correct
31 Correct 22 ms 592 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 28 ms 21916 KB Output is correct
34 Correct 49 ms 37752 KB Output is correct
35 Correct 44 ms 37772 KB Output is correct
36 Correct 48 ms 37804 KB Output is correct
37 Correct 54 ms 37816 KB Output is correct
38 Correct 41 ms 37900 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 209 ms 17384 KB Output is correct
5 Correct 881 ms 37868 KB Output is correct
6 Correct 615 ms 6476 KB Output is correct
7 Correct 781 ms 37796 KB Output is correct
8 Correct 537 ms 13196 KB Output is correct
9 Correct 853 ms 37896 KB Output is correct
10 Correct 1274 ms 37848 KB Output is correct
11 Correct 1287 ms 37816 KB Output is correct
12 Correct 1110 ms 37788 KB Output is correct
13 Correct 977 ms 37816 KB Output is correct
14 Correct 1080 ms 37760 KB Output is correct
15 Correct 842 ms 37796 KB Output is correct
16 Correct 787 ms 37816 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 208 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 208 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 11 ms 680 KB Output is correct
28 Correct 22 ms 592 KB Output is correct
29 Correct 20 ms 592 KB Output is correct
30 Correct 16 ms 592 KB Output is correct
31 Correct 22 ms 592 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 28 ms 21916 KB Output is correct
34 Correct 49 ms 37752 KB Output is correct
35 Correct 44 ms 37772 KB Output is correct
36 Correct 48 ms 37804 KB Output is correct
37 Correct 54 ms 37816 KB Output is correct
38 Correct 41 ms 37900 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 1 ms 272 KB Output is correct
42 Correct 298 ms 17428 KB Output is correct
43 Correct 871 ms 37760 KB Output is correct
44 Correct 576 ms 6444 KB Output is correct
45 Correct 928 ms 37788 KB Output is correct
46 Correct 572 ms 13248 KB Output is correct
47 Correct 962 ms 37816 KB Output is correct
48 Correct 1206 ms 37904 KB Output is correct
49 Correct 1054 ms 37768 KB Output is correct
50 Correct 1137 ms 37768 KB Output is correct
51 Correct 804 ms 37868 KB Output is correct
52 Correct 956 ms 37844 KB Output is correct
53 Correct 830 ms 37904 KB Output is correct
54 Correct 654 ms 37804 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Incorrect 94 ms 37648 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 139 ms 30120 KB Output isn't correct
4 Halted 0 ms 0 KB -