Submission #821441

#	Time	Username	Problem	Language	Result	Execution time	Memory
821441		yeyso	Rainforest Jumps (APIO21_jumps)	C++14	33 / 100	4078 ms	25420 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
vector<vector<int>> adj;
int n = 0;
void init(int N, vector<int> H) {
    n = N;
    stack<pair<int, int>> s;
    vector<vector<int>> adj0(N, vector<int>());
    for (int i = 0; i < N; i ++) {
        while (!s.empty() && s.top().first < H[i]){
            s.pop();
        }
        if (!s.empty()){
            adj0[i].push_back(s.top().second);
        }
        s.push({H[i], i});
    }
 
    while(!s.empty()){
        s.pop();
    }
 
    for (int i = N; i >= 0; i --) {
        while (!s.empty() && s.top().first < H[i]){
            s.pop();
        }
        if (!s.empty()){
            adj0[i].push_back(s.top().second);
        }
        s.push({H[i], i});
    }

    adj = adj0;

    /*for(int i = 0; i < adj.size(); i ++){
        cout << i + 1<< " | ";
        for(int j = 0; j < adj[i].size(); j ++){
            cout << adj[i][j] + 1 << " ";
        } cout << "\n";
    }*/
    
}

int minimum_jumps(int A, int B, int C, int D) {
    queue<pair<int, int>> q;
    for(int i = A; i <= B; i ++){
        q.push({0, i});
    }
    int node = 0; int dist = 0;
    vector<int> v(n, 0);
    while(!q.empty()){
        node = q.front().second;
        dist = q.front().first;
        //cout << node << "\n";
        q.pop();
        if(node >= C && node <= D){
            return dist;
            break;
        }
        if(!v[node]){
            v[node] = 1;
            for(int i = 0; i < adj[node].size(); i ++){
                q.push({dist + 1, adj[node][i]});
            }
        }
    }
    return -1;
}
/*
g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp

7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2

*/

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int i = 0; i < adj[node].size(); i ++){
      |                            ~~^~~~~~~~~~~~~~~~~~

• 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