Submission #1223613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223613		sokratisi	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	419 ms	57588 KiB

jumps

#include "jumps.h"
#include <vector>
#include <stack>
#include <cstdio>
#include <queue>

using namespace std;

int n, in;
vector<int> h;
vector<bool> vis;
vector<vector<int>> adj;
int sparse1[200005][20], sparse2[200005][20]; // maybe more

void create_graph() {
    stack<int> s;
    for (int i = 0; i < n; i++) {
        // if (h[i] == 1) in = i;
        while (s.size() > 0 && h[i] > h[s.top()]) {
            adj[s.top()].push_back(i);
            s.pop();
        }
        s.push(i);
    }
    while (s.size() > 0) s.pop();
    for (int i = n-1; i >= 0; i--) {
        while (s.size() > 0 && h[i] > h[s.top()]) {
            adj[s.top()].push_back(i);
            s.pop();
        }
        s.push(i);
    }
}

// void print_graph() {
//     for (int i = 0; i < n; i++) {
//         printf("%d: ", i);
//         for (auto u: adj[i]) printf("%d ", u);
//         printf("\n");
//     }
// }

// void bfs() {
//     for (int i = 0; i < n+2; i++) dist[i] = 1e9;
//     for (int i = 0; i < n+2; i++) vis[i] = false;
//     queue<int> q;
//     q.push(n);
//     dist[n] = 0;
//     while (!q.empty()) {
//         int cur = q.front();
//         q.pop();
//         if (vis[cur]) continue;
//         vis[cur] = true;
//         for (auto u: adj[cur]) {
//             q.push(u);
//             dist[u] = min(dist[u], dist[cur]+1);
//         }
//     }
// }

// void print_dist() {
//     for (int i = 0; i < n+2; i++) {
//         printf("%d -> %d\n", i, dist[i]);
//     }
// }

void calc_sparse1(int s) {
    vis[s] = true;
    for (auto u: adj[s]) {
        if (!vis[u]) calc_sparse1(u);
    }
    sparse1[s][0] = s;
    for (auto u: adj[s]) {
        if (h[u] > h[sparse1[s][0]]) sparse1[s][0] = u;
    }
    for (int i = 1; i < 20; i++) sparse1[s][i] = sparse1[sparse1[s][i-1]][i-1];
}

void calc_sparse2(int s) {
    vis[s] = true;
    for (auto u: adj[s]) {
        if (!vis[u]) calc_sparse2(u);
    }
    if (adj[s].size() == 0) sparse2[s][0] = s;
    else {
        sparse2[s][0] = adj[s][0];
        for (auto u: adj[s]) {
            if (h[u] < h[sparse2[s][0]]) sparse2[s][0] = u;
        }
    }
    for (int i = 1; i < 20; i++) sparse2[s][i] = sparse2[sparse2[s][i-1]][i-1];
}

// void print_sparse() {
//     printf("SPARSE2:\n");
//     for (int i = 0; i < n; i++) {
//         printf("%d: ", i);
//         for (int j = 0; j < 4; j++) printf("%d ", sparse2[i][j]);
//         printf("\n");
//     }
//     printf("\n\n");
// }

void init(int Num, vector<int> Height) {
    n = Num;
    h = Height;
    adj.resize(n); // place n is fake out and place n+1 is fake in
    // dist.resize(n+2);
    vis.resize(n);
    create_graph();
    for (int i = 0; i < n; i++) if (!vis[i]) calc_sparse1(i);
    for (int i = 0; i < n; i++) vis[i] = false;
    for (int i = 0; i < n; i++) if (!vis[i]) calc_sparse2(i);
    // print_graph();
    // print_sparse();
}

int minimum_jumps(int a, int b, int c, int d) {
    int ans = 0;
    for (int i = 19; i >= 0; i--) {
        if (h[sparse1[a][i]] < h[c]) {
            a = sparse1[a][i];
            ans += 1<<i;
        }
    }

    if (sparse1[a][0] == c) return ans+1;
    // if all are greater you are fucked
    // just choose the smallest of the two
    for (int i = 19; i >= 0; i--) {
        if (h[sparse2[a][i]] < h[c]) {
            a = sparse2[a][i];
            ans += 1<<i;
        }
    }
    bool okay = false;
    for (auto u: adj[a]) if (h[u] <= h[c]) okay = true;
    if (okay) return ans + 1;
    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