Submission #744469

#	Time	Username	Problem	Language	Result	Execution time	Memory
744469		speedyArda	Rainforest Jumps (APIO21_jumps)	C++14	25 / 100	1101 ms	199416 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, BIT = 18;
vector< vector<int> > adj(MAXN), revadj(MAXN);
vector< vector<int> > dist(SMALL, vector<int>(SMALL, 1e9));
int sparse[SMALL][12][SMALL];
int outdeg[MAXN];
int dfs_dist[MAXN];
bool dfs_visited[MAXN];
int jmp[MAXN][BIT];
int lg[MAXN];
int n;

int lca(int a, int b)
{
  if(dfs_dist[a] < dfs_dist[b])
    swap(a, b);
  int diff = dfs_dist[a] - dfs_dist[b];
  for(int i = 0; i < BIT; i++)
  {
    if((1 << i) & diff)
      a = jmp[a][i];
  }
  if(a == b)
    return a;
  for(int i = BIT - 1; i >= 0; i--)
  {
    if(jmp[a][i] != jmp[b][i])
    {
      a = jmp[a][i];
      b = jmp[b][i];
    }
  }
  return jmp[a][0];
}
void dfs(int v, int p)
{
  dfs_visited[v] = true;
  jmp[v][0] = p;
  for(int i = 1; i < BIT; i++)
    jmp[v][i] = jmp[jmp[v][i - 1]][i - 1];
  
  for(int e : revadj[v])
  {
    if(e == p || dfs_visited[e])
      continue;
      dfs_dist[e] = dfs_dist[v] + 1;
      dfs(e, v);
  }
}
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);
      outdeg[v]++;

    }
    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);
      outdeg[v]++;
    }
    curr.push(i);
  }
  int last = 0;
  for(int i = 0; i < N; i++)
  {
    if(outdeg[i] == 0) // We will have only one such node which is the biggest element in the array
      last = i;
  }
  dfs_dist[last] = 0;
  dfs(last, MAXN - 1);
  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;
  }
  if(C == D)
  {
    if(A == B) // Subtask 5
    {
        int top = lca(A, C);
        if(top != A && top != C)
          return -1;
        //cout << dfs_dist[A] << " " << dfs_dist[C] << "\n";
        return max(dfs_dist[A], dfs_dist[C]) - min(dfs_dist[A], dfs_dist[C]);
    }
  } 
  //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;
}

Compilation message (stderr)

jumps.cpp: In function 'void dfs(int, int)':
jumps.cpp:48:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |     if(e == p || dfs_visited[e])
      |     ^~
jumps.cpp:50:7: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   50 |       dfs_dist[e] = dfs_dist[v] + 1;
      |       ^~~~~~~~

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