Submission #1223397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223397		sokratisi	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4088 ms	16020 KiB

jumps

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

using namespace std;

int n;
vector<int> h, dist;
vector<bool> vis;
vector<vector<int>> adj;

void create_graph() {
    stack<int> s;
    for (int i = 0; i < n; 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 init(int Num, vector<int> Height) {
    n = Num;
    h = Height;
    adj.resize(n+2); // place n is fake out and place n+1 is fake in
    dist.resize(n+2);
    vis.resize(n+2);
    create_graph();
    // print_graph();
}

int minimum_jumps(int a, int b, int c, int d) {
    for (int i = a; i <= b; i++) adj[n].push_back(i);
    for (int i = c; i <= d; i++) adj[i].push_back(n+1);
    bfs();
    // print_dist();
    adj[n].clear();
    for (int i = c; i <= d; i++) adj[i].pop_back();
    if (dist[n+1] < 1e8) return dist[n+1]-2;
    return -1;
}

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