Submission #1223370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223370		SpyrosAliv	Rainforest Jumps (APIO21_jumps)	C++20	Compilation error	0 ms	0 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) {
    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;
}

int main() {
    cin >> n;
    vector<int> H(n);
    for (int i = 0; i < n; i++) cin >> H[i];
    init(n, H);
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << minimum_jumps(a, b, c, d) << "\n";
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccvPma0m.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccZGX1lF.o:jumps.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status