Submission #744459

#	Time	Username	Problem	Language	Result	Execution time	Memory
744459		speedyArda	Rainforest Jumps (APIO21_jumps)	C++14	37 / 100	4035 ms	199168 KiB

jumps

#include "jumps.h"
#include <vector>
#include "bits/stdc++.h"
using namespace std;
bool sub1 = true;
const int MAXN = 2e5+5, SMALL = 2e3+5;
vector< vector<int> > adj(MAXN), revadj(MAXN);
vector< vector<int> > dist(SMALL, vector<int>(SMALL, 1e9));
int sparse[SMALL][12][SMALL];
int indeg[MAXN];
int lg[MAXN];
int n;
void init(int N, vector<int> H) {
  lg[1] = 0;
  for(int i = 2; i < MAXN; i++)
    lg[i] = lg[i / 2] + 1;
  n = N;
  stack<int> curr;
  for(int i = 0; i < N; i++)
  {
    if(H[i] != i + 1)
      sub1 = false;
    while(!curr.empty() && H[curr.top()] < H[i])
    {
      int v = curr.top();
      curr.pop();
      adj[v].push_back(i);
      revadj[i].push_back(v);
      indeg[i]++;

    }
    curr.push(i);
    
  }
  while(!curr.empty())
  {
    curr.pop();
  }

  for(int i = N - 1; i >= 0; i--)
  {
    while(!curr.empty() && H[curr.top()] < H[i])
    {
      int v = curr.top();
      curr.pop();
      adj[v].push_back(i);
      revadj[i].push_back(v);
      indeg[i]++;
    }
    curr.push(i);
  }

  if(N <= 2000) {
    for(int i = 0; i < N; i++)
    {
      queue< int > ord;
      vector<bool> visited(N, false);
      dist[i][i] = 0;
      visited[i] = true;
      ord.push(i);
      while(!ord.empty())
      {
        int v = ord.front();
        ord.pop();
        for(int e : revadj[v])
        {
          if(visited[e])
            continue;
          dist[e][i] = dist[v][i] + 1;
          visited[e] = true;
          ord.push(e);
        }
      }
    }
    /*for(int i = 0; i < N; i++)
    {
      for(int a = 0; a < N; a++)
        cout << i << " " << a <<": " << dist[i][a] << "\n";
    }*/
    for(int i = 0; i < N; i++)
    {
      for(int a = 0; a < N; a++)
          sparse[i][0][a] = dist[i][a];
      for(int bit = 1; bit <= 11; bit++)
      {
        for(int j = 0; j + (1 << bit) - 1 < N; j++) {
          sparse[i][bit][j] = min(sparse[i][bit - 1][j], sparse[i][bit - 1][j + (1 << (bit - 1))]);
          //cout << i << " " << bit << " " << j << " " << sparse[i][bit][j] << "\n";
        }
      }
    }
  }
}

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

  if(sub1) // Subtask 1
  {
    return C - B;
  }
  //Subtask 2, 3
  if(n <= 2000) {
    int ans = 1e9;
    for(int i = A; i <= B; i++)
    {
      int add = lg[D - C + 1];
      ans = min(ans, min(sparse[i][add][C], sparse[i][add][D - (1 << add) + 1]));
        //cout << i << " " << add << " " << sparse[i][add][C] << " " << sparse[i][add][D - (1 << add) + 1] << "\n";
    }
    if(ans == 1e9)  
      ans = -1;
    return ans;
  }

  //Subtask 4
  vector<bool> visited(n, false);
  vector<int> dist(n, 1e9);
  queue<int> curr;
  for(int i = C; i <= D; i++)
  { 
    dist[i] = 0;
    curr.push(i);
    visited[i] = true;
  }
  while(!curr.empty())
  {
    int v = curr.front();
    curr.pop();
    for(int e : revadj[v])
    {
      if(visited[e])
        continue;
      visited[e] = true;
      dist[e] = dist[v] + 1;
      curr.push(e);
    }
  }

  int ans = 1e9;
  for(int i = A; i <= B; i++)
    ans = min(ans, dist[i]);
  if(ans == 1e9)
    ans = -1;
  return ans;
}

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