Submission #728044

#	Time	Username	Problem	Language	Result	Execution time	Memory
728044		grossly_overconfident	Rainforest Jumps (APIO21_jumps)	C++17	21 / 100	4040 ms	24132 KiB

jumps

//#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
vector<vector<int>> adj;

void init(int n, vector<int> H){
    adj.resize(n);
    for (int i = 0; i < n; ++i){
        for (int j = i; j < n; ++j){
            if (H[j] > H[i]){
                adj[i].push_back(j);
                break;
            }
        }
        for (int j = i; j >= 0; --j){
            if (H[j] > H[i]){
                adj[i].push_back(j);
                break;
            }
        }
    }
}


int minimum_jumps(int a, int b, int c, int d){
    queue<pair<int, int>> q;
    unordered_set<int> s, f;
    vector<bool> v(adj.size());
    for (int i = a; i <= b; ++i){
        s.insert(i);
    }
    for (int i = c; i <= d; ++i){
        f.insert(i);
    }
    for (int i : s){
        q.push({0, i});
    }
    while (!q.empty()){
        auto t = q.front();
        q.pop();
        if (v[t.second]){
            continue;
        }
        v[t.second] = true;
        if (f.find(t.second) != f.end()){
            return t.first;
        }
        for (int i : adj[t.second]){
            q.push({t.first + 1, i});
        }
    }
    return -1;
}



/*
signed main(){
    
    //cin.tie(0);
    //iostream::sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector<int> k(n);
    for (int i = 0; i < n; ++i){
        cin >> k[i];
    }
    init(n, k);
    for (int i = 0; i < q; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << endl;
    }


    return 0;
}
*/

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