Submission #724900

#	Time	Username	Problem	Language	Result	Execution time	Memory
724900		yeyso	Rainforest Jumps (APIO21_jumps)	C++14	21 / 100	4019 ms	23768 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;
    vector<vector<int>> aadj(n, vector<int>());
    for(int i = 0; i < h.size(); i ++){
        for(int j = i + 1; j < h.size(); j ++){
            if(h[j] > h[i]){
                aadj[i].push_back(j);
                break;
            }
        }
        for(int j = i - 1; j >= 0; j --){
            if(h[j] > h[i]){
                aadj[i].push_back(j);
                break;
            }
        }
    }

    adj = aadj;

    /*for(int i = 0; i < adj.size(); i ++){
        for(int j = 0; j < adj[i].size(); j ++){
            cout << adj[i][j] << " ";
        }
        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});
        //cout << i << " ";
    }
    int node = 0; int dist = 0;
    vector<int> v(n, 0);
    while(!q.empty()){
        node = q.front().second; dist = q.front().first;
        q.pop();
        if(!v[node]){
            //cout << node;
            v[node] = 1;
            if(c <= node and node <= d){
                return dist;
                break;
            }
            for(int i = 0; i < adj[node].size(); i ++){
                q.push({dist + 1, adj[node][i]});
            }
        }
    }

    return -1;
}
/*
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 'void init(int, std::vector<int>)':
jumps.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 0; i < h.size(); i ++){
      |                    ~~^~~~~~~~~~
jumps.cpp:11:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for(int j = i + 1; j < h.size(); j ++){
      |                            ~~^~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:54:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(int i = 0; i < adj[node].size(); i ++){
      |                            ~~^~~~~~~~~~~~~~~~~~

• 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