Submission #1223373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223373		SpyrosAliv	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	285 ms	27876 KiB

jumps

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

const int INF = 1e9;
int n;
vector<int> h;
vector<int> toL, toR;
vector<vector<int>> g, revG;
vector<int> deg;

void init(int N, vector<int> H) {
    n = N;
    h = {0};
    toL.assign(n+1, 0);
    toR.assign(n+1, 0);
    for (auto x: H) h.push_back(x);
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && h[st.top()] <= h[i]) st.pop();
        if (st.empty()) toL[i] = 0;
        else toL[i] = st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && h[st.top()] <= h[i]) st.pop();
        if (st.empty()) toR[i] = n+1;
        else toR[i] = st.top();
        st.push(i);
    }
    deg.assign(n+1, 0);
    revG.resize(n+1);
    g.resize(n+1);
    for (int i = 1; i <= n; i++) {
        if (toL[i] >= 1) {
            g[i].push_back(toL[i]);
            revG[toL[i]].push_back(i);
            deg[i]++;
        }
        if (toR[i] <= n) {
            g[i].push_back(toR[i]);
            revG[toR[i]].push_back(i);
            deg[i]++;
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    return c - b;
    a++;
    b++;
    c++;
    d++;
    queue<int> q;
    vector<int> currDeg = deg;
    for (int i = 1; i <= n; i++) {
        if (currDeg[i] == 0) q.push(i);
    }
    vector<int> dp(n+1, INF);
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        if (curr >= c && curr <= d) dp[curr] = 0;
        for (auto next: g[curr]) {
            dp[curr] = min(dp[curr], 1 + dp[next]);
        }
        for (auto next: revG[curr]) {
            currDeg[next]--;
            if (currDeg[next] == 0) q.push(next); 
        }
    }
    int mn = INF;
    for (int i = a; i <= b; i++) {
        mn = min(mn, dp[i]);
    }
    if (mn == INF) return -1;
    else return mn;
}

• Subtask 1: 4 / 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