Submission #940016

#	Time	Username	Problem	Language	Result	Execution time	Memory
940016		bobbilyking	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	778 ms	80292 KiB

jumps

#include "jumps.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define all(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }

template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }

const ll NN = 2e5 + 10;
const ll INF = 1e9 + 1;
ll n;

vl graph[NN];

const ll L = 20;

ll lift[NN][L];
ll liftSmall[NN][L];

ll h[NN];

void init(int _N, std::vector<int> H) {
    n = _N;
    copy(all(H), h);
    vl lst(n);
    F(i, 0, n) {
        lst[i] = i - 1;
        while (lst[i] != -1 and H[lst[i]] < H[i]) lst[i] = lst[lst[i]];
        if (lst[i] != -1) graph[i].push_back(lst[i]);
    }
    FD(i, n-1, -1) {
        lst[i] = i + 1;
        while (lst[i] != n and H[lst[i]] < H[i]) lst[i] = lst[lst[i]];
        if (lst[i] != n) graph[i].push_back(lst[i]);
    }

    vl idx(n); iota(all(idx), 0ll);
    sort(all(idx), [&](ll a, ll b) {
        return H[a] > H[b];
    });

    F(j, 0, L) lift[n][j] = liftSmall[n][j] = n;
    
    for (auto i: idx) {
        lift[i][0] = liftSmall[i][0] = n;
        sort(all(graph[i]), [&](ll a, ll b) {
            return H[a] > H[b];
        });
        if (graph[i].size() >= 1) {
            lift[i][0] = graph[i][0];
        }
        if (graph[i].size() == 2) liftSmall[i][0] = graph[i][1];

        F(j, 1, L) {
            lift[i][j] = lift[lift[i][j-1]][j-1];
            liftSmall[i][j] = liftSmall[liftSmall[i][j-1]][j-1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (A == B and C == D) {
        ll cost = 0;
        FD(l, L-1, -1) {
            if (lift[A][l] != n and h[lift[A][l]] <= h[C]) {
                A = lift[A][l];
                cost += 1 << l;
            }
        }

        FD(l, L-1, -1) {
            if (liftSmall[A][l] != n and h[liftSmall[A][l]] <= h[C]) {
                A = liftSmall[A][l];
                cost += 1 << l;
            }
        }

        if (A != C) return -1;
        return cost;

    } else return -1;
}

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