Submission #821578

#	Time	Username	Problem	Language	Result	Execution time	Memory
821578		yeyso	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	298 ms	179840 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
vector<vector<int>> adj;
vector<vector<int>> radj;
int n = 0;
vector<vector<int>> st0;
vector<vector<int>> st1;
vector<int> visited;
vector<int> h;
void dfs0(int u, int v){
    if(!visited[u]){
        visited[u] = 1;
        st0[u][0] = v;
        //cout << h[u] << " " << h[v] << "\n";
        for(int z = 1; z <= ceil(log2(n)); z ++){
            st0[u][z] = st0[st0[u][z-1]][z-1];
        }
        for(int i = 0; i < radj[u].size(); i ++){
            int highedge = 1;
            for(int j = 0; j < adj[radj[u][i]].size(); j ++){
                if(h[adj[radj[u][i]][j]] > h[u]){
                    highedge = 0;
                    //break;
                }
            }
            if(highedge){
                dfs0(radj[u][i], u);
            }
        }
    }
}
void dfs1(int u, int v){
    if(!visited[u]){
        visited[u] = 1;
        st1[u][0] = v;
        //cout << h[u] << " " << h[v] << "\n";
        for(int z = 1; z <= ceil(log2(n)); z ++){
            st1[u][z] = st1[st1[u][z-1]][z-1];
        }
        for(int i = 0; i < radj[u].size(); i ++){
            int lowedge = 1;
            for(int j = 0; j < adj[radj[u][i]].size(); j ++){
                if(h[adj[radj[u][i]][j]] < h[u]){
                    lowedge = 0;
                    //break;
                }
            }
            if(lowedge){
                dfs1(radj[u][i], u);
            }
        }
    }
}
void init(int N, vector<int> H) {
    n = N;
    h = H;
    stack<pair<int, int>> s;
    vector<vector<int>> adj0(N, vector<int>());
    int highest = 0;
    int idx = 0;
    vector<vector<int>> radj0(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);

            radj0[s.top().second].push_back(i);
        }
        s.push({H[i], i});

        if(H[i] > highest){
            highest = H[i];
            idx = 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);

            radj0[s.top().second].push_back(i);
        }
        s.push({H[i], i});
    }

    adj = adj0;
    radj = radj0;
    vector<vector<int>> st(n, vector<int>(ceil(log2(n)), 0));
    st0 = st;
    st1 = st;
    vector<int> v(N, 0);
    visited = v;
    dfs0(idx, idx);
    visited = v;
    dfs1(idx, idx);
    /*for(int i = 0; i < st1.size(); i ++){
        for(int j = 0; j < st1[i].size(); j ++){
            cout << h[st1[i][j]] << " ";
        } cout << "\n";
    }*/
}

int minimum_jumps(int A, int B, int C, int D) {

    int jumps = 0;
    int u = A;
    for (int i = ceil(log2(n)); i >= 0; --i) {
        if(h[st0[u][i]] < h[C]){
            u = st0[u][i];
            jumps += (1 << i);
        }
    }
    // If the first sparse table is all we need, we're done
    if(st0[u][0] == C){
        return jumps + 1;
    } else {
        // Add one jump to start at the next sparse table
        u = st0[u][0];
        jumps += 1;
        for (int i = ceil(log2(n)); i >= 0; --i) {
            if(h[st1[u][i]] < h[C]){
                u = st1[u][i];
                jumps += (1 << i);
            }
        }

        if(st1[u][0] == C){
            return jumps + 1;
        }
    }
    return -1;
    //return u;
    /*if(jumps){
        return jumps + 1;
    } else {
        return 0;
    }*/
    /*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]});
            }
        }
    }*/
}
/*
g++ -std=gnu++17 -O2 -pipe -o jumps jumps.cpp stub.cpp

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

0  1  2  3  4  5  6 7 8 9 10 11 12 3 4 5 16 17 18 19
20 5
20 18 16 14 12 10 8 6 4 2 1 3 5 7 9 11 13 15 17 19 
4 4 19 19
14 14 0 0
3 3 9 9
4 4 3 3
1 1 9 9
*/

Compilation message (stderr)

jumps.cpp: In function 'void dfs0(int, int)':
jumps.cpp:20:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:22:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void dfs1(int, int)':
jumps.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 0; i < radj[u].size(); i ++){
      |                        ~~^~~~~~~~~~~~~~~~
jumps.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int j = 0; j < adj[radj[u][i]].size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~

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