Submission #1125350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125350		SamueleVid	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	211 ms	66688 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int N;
vector<int> H;
vector<vector<int>> adj;
bool first_subtask = true;

constexpr ll PW = 262144;
constexpr ll LOG = 20;

struct segment {
    vector<ll> seg;
    segment() {
        seg.assign(2 * PW, 1e9);
    }

    void update(int x, ll d) {
        x += PW;
        seg[x] = d;
        x /= 2;
        while (x >= 1) {
            seg[x] = min(seg[2 * x], seg[2 * x + 1]);
            x /= 2;
        }
    }

    ll query(int l, int r) {
        l += PW; r += PW;
        ll sol = 1e9;
        while (l <= r) {
            if (l % 2 == 1) {
                sol = min(sol, seg[l]);
                l ++;
            }
            if (r % 2 == 0) {
                sol = min(sol, seg[r]);
                r --;
            }
            l /= 2; r /= 2;
        }
        return sol;
    }

    void clear() {
        for (int i = 0; i < 2 * PW; i ++) seg[i] = 1e9;
    }
};

struct binlift {
    int N, LOG;
    vector<int> p;
    vector<int> depth;
    vector<vector<int>> bl;
    vector<vector<int>> adj;
    
    binlift() {}
    binlift(int N_, int LOG_, vector<int> p_) {
        N = N_;
        LOG = LOG_;
        p = p_;
        depth.resize(N);
        bl.assign(LOG_, vector<int>(N));
        adj.resize(N);
        for (int i = 0; i < N; i ++) {
            if (p[i] != -1) adj[p[i]].push_back(i);
        }

        for (int i = 0; i < N; i ++) {
            if (p[i] == -1) {
                depth[i] = 0;
                dfs_depth(i);
            }
        }

        for (int i = 0; i < N; i ++) {
            bl[0][i] = (p[i] != -1) ? p[i] : i;
        }

        for (int p = 1; p < LOG; p ++) {
            for (int i = 0; i < N; i ++) {
                bl[p][i] = bl[p - 1][bl[p - 1][i]];
            }
        }        
    }

    void dfs_depth(int u) {
        for (auto x : adj[u]) {
            depth[x] = depth[u] + 1;
            dfs_depth(x);
        }
    }

    int n_th_ancestor(int u, int n) {
        for (int i = LOG - 1; i > 0; i --) {
            if (n & (1 << i)) u = bl[i][u];
        }
        return u;
    }
};

segment seg;

vector<int> p_max;
vector<int> p_dx;

binlift bl_max, bl_dx;

void init(int N, vector<int> H) {
    ::N = N;
    ::H = H;

    vector<int> inv_H(N + 1);
    for (int i = 0; i < N; i ++) inv_H[H[i]] = i;

    p_max.assign(N, -1);
    p_dx.assign(N, -1);

    adj.resize(N);
    // a destra
    for (int i = N - 1; i >= 0; i --) {
        int u = seg.query(H[i] + 1, N);
        if (u != 1e9) {
            adj[i].push_back(u);
            p_dx[i] = u;
            p_max[i] = u;
        }
        seg.update(H[i], i);
    }

    seg.clear();
    // a sinistra
    for (int i = 0; i < N; i ++) {
        int u = -seg.query(H[i] + 1, N);
        if (u != -1e9)  {
            adj[i].push_back(u);
            if (p_max[i] != -1 && H[u] > H[p_max[i]]) p_max[i] = u; 
        }
        seg.update(H[i], -i);
    }

    bl_max = binlift(N, LOG, p_max);
    bl_dx = binlift(N, LOG, p_dx);
}

int minimum_jumps(int A, int B, int C, int D) {
    // A == B e C == D

    int k = -1;
    for (int p = PW; p >= 1; p /= 2) {
        int u = bl_max.n_th_ancestor(A, (p + k));
        if (bl_dx.depth[C] > bl_dx.depth[u]) continue;
        int v = bl_dx.n_th_ancestor(u, bl_dx.depth[u] - bl_dx.depth[C]);
        if (v == C) k += p;
    }

    if (k == -1) return -1;

    int u = bl_max.n_th_ancestor(A, k);

    int sol = (bl_dx.depth[u] - bl_dx.depth[C]) + (bl_max.depth[A] - bl_max.depth[u]);
    return sol;

}

• 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