Submission #1035213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035213		_8_8_	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	156 ms	131900 KiB

jumps

#include "jumps.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

const int B = 20;
int n;
vector<vector<int>> build(vector<vector<int>> g,vector<int>rt){
    vector<vector<int>> up(n+1);
    function<void(int,int )> dfs = [&](int v,int pr) {
        up[v].resize(B);
        up[v][0] = pr;
        for(int i = 1;i < B;i++){
            up[v][i] = up[up[v][i - 1]][i - 1];
        }
        for(int to:g[v]) {  
            dfs(to,v);
        }
    };
    for(int i:rt) {
        dfs(i,i);
    }
    return up;
}
vector<vector<int>> up,up1;
void init(int N, vector<int> H) {
    n = N;
    vector<int> st,rt;
    vector<vector<int>> G(n);
    for(int i = 0;i < N;i++) {
        while(!(int)st.empty() && H[st.back()] < H[i]) {
            st.pop_back();
        }
        if(st.empty()){
            rt.push_back(i);
        }else {
            G[st.back()].push_back(i);
        }
        st.push_back(i);
    }
    up = build(G,rt);
    for(int i = 0;i < n;i++){
        G[i].clear();
    }
    rt.clear();
    st.clear();
    for(int i = N - 1;i >= 0;i--){
        while(!st.empty() && H[st.back()] < H[i]){
            st.pop_back();
        }
        if(st.empty()){
            rt.push_back(i);
        }else{
            G[st.back()].push_back(i);
        }
        st.push_back(i);
    }
    up1 = build(G,rt);
}
int check(int ver,int C,int D){
    int res =0;
    for(int i = B - 1;i >= 0;i--){
        if(up1[ver][i] < C){
            ver = up1[ver][i];
            res += (1 << i);
        }
    }
    res++;
    ver = up1[ver][0];
    return (ver >= C && ver <= D ? res : -1);
}
int minimum_jumps(int A, int B, int C, int D) {
    int ver = B;
    for(int i = B - 1;i >= 0;i--){
        if(up[ver][i] >= A && check(ver,C,D) != -1){
            ver = up[ver][i];
        }
    }
    return check(ver,C,D);
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19