Submission #823728

#	Time	Username	Problem	Language	Result	Execution time	Memory
823728		yeyso	Rainforest Jumps (APIO21_jumps)	C++14	60 / 100	4070 ms	135852 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;
        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);
            }
        }
    }
}
int subtask1 = 1;
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>());
    // Monotonic stack to construct adjacency list in O(n)
    for (int i = 0; i < N; i ++) {
        if(i > 0){
            if(H[i] != i + 1){
                subtask1 = 0;
            }
        }
        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 - 1; 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)) + 1, 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) {
    // In this case, our O(logn) algorithm for subtask 5
    if(A == B and C == 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
        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;
    // Otherwise, if it's subtask 1, we do our dumb solution
    } else if(subtask1){
        return C - B;
        // Now it's only subtask 2, 3 or 4 so we do BFS
    } else {
        //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> vi(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(!vi[node]){
                vi[node] = 1;
                for(int i = 0; i < adj[node].size(); i ++){
                    q.push({dist + 1, adj[node][i]});
                }
            }
        }

        return -1;
    }
}

Compilation message (stderr)

jumps.cpp: In function 'void dfs0(int, int)':
jumps.cpp:19:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         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 ++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:173:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |                 for(int i = 0; i < adj[node].size(); i ++){
      |                                ~~^~~~~~~~~~~~~~~~~~

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