Submission #1208820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208820		spacewalker	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	735 ms	138836 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> next_greater(const vector<int> &v) {
  int n = v.size();
  vector<int> ans(n, -1);
  vector<int> possible_next{n - 1};
  for (int i = n - 2; i >= 0; --i) {
    while (!possible_next.empty() && v[i] >= v[possible_next.back()])
      possible_next.pop_back();
    if (!possible_next.empty())
      ans[i] = possible_next.back();
    possible_next.push_back(i);
  }
  return ans;
}

using interval = pair<int, int>;

interval onion(interval a, interval b) {
  return {min(a.first, b.first), max(a.second, b.second)};
}

interval intersection(interval a, interval b) {
  return {max(a.first, b.first), min(a.second, b.second)};
}

bool has_overlap(interval a, interval b) {
  return !(a.second < b.first || b.second < a.first);
}

// fn ((a, b), (a, b)) { (a, b) }
// let onion((x, y), (z, w)) = (min(x, z), max(y, w))

struct Jumper {
  vector<vector<int>> tree_ch;
  vector<vector<int>> locations;
  vector<int> depth;
  vector<pair<int, int>> reachable_from;
  vector<vector<pair<int, int>>> ranges_crossed;
  void init_reachable_from(int v) {
    reachable_from[v] = {v, v};
    for (int ch : tree_ch[v]) {
      depth[ch] = depth[v] + 1;
      init_reachable_from(ch);
      reachable_from[v] = onion(reachable_from[v], reachable_from[ch]);
    }
  }
  Jumper() {}
  Jumper(int root, const vector<int> &tree,
         const vector<pair<int, int>> init_ranges)
      : tree_ch(tree.size()), locations(20, vector(tree.size(), -1)),
        depth(tree.size()),
        reachable_from(tree.size(), {-1, -1}),
        ranges_crossed(
            20, vector(tree.size(), pair<int, int>{tree.size() + 100, -1})) {
    for (int i = 0; i < tree.size(); ++i)
      if (tree[i] != -1) {
        tree_ch[tree[i]].push_back(i);
        locations[0][i] = tree[i];
      }

    init_reachable_from(root);
    ranges_crossed[0] = init_ranges;
    for (int i = 0; i < tree.size(); ++i) {
      int layer = 0;
      // cerr << "layer " << layer << " " << i << " -> " << locations[layer][i]
      //      << " (" << ranges_crossed[layer][i].first << ", "
      //      << ranges_crossed[layer][i].second << ")" << endl;
    }
    for (int layer = 1; layer < locations.size(); ++layer) {
      for (int i = 0; i < tree.size(); ++i)
        if (locations[layer - 1][i] != -1) {
          locations[layer][i] = locations[layer - 1][locations[layer - 1][i]];
          ranges_crossed[layer][i] =
              onion(ranges_crossed[layer - 1][i],
                    ranges_crossed[layer - 1][locations[layer - 1][i]]);
          // cerr << "layer " << layer << " " << i << " -> " << locations[layer][i]
          //      << " (" << ranges_crossed[layer][i].first << ", "
          //      << ranges_crossed[layer][i].second << ")" << endl;
        }
    }
  }

  int last_inside(int v, interval i) {
    int cv = v;
    for (int layer = locations.size() - 1; layer >= 0; --layer) {
      if (locations[layer][cv] != -1 && i.first <= locations[layer][cv] &&
          locations[layer][cv] <= i.second)
        cv = locations[layer][cv];
    }
    return cv;
  }

  // {vertex, # of steps taken, interval visited}
  tuple<int, int, interval> last_before_overlapping(int v, interval i) {
    int cv = v;
    auto crange = ranges_crossed[0][v];
    int dist = 0;
    for (int layer = locations.size() - 1; layer >= 0; --layer) {
      if (locations[layer][cv] != -1 &&
          !has_overlap(onion(crange, ranges_crossed[layer][cv]), i)) {
        crange = onion(crange, ranges_crossed[layer][cv]);
        cv = locations[layer][cv];
        dist += (1 << layer);
      }
    }
    return {cv, dist, crange};
  }

  int direct_len(int v, interval i) {
    auto [dst, dist, _] = last_before_overlapping(v, i);
    if (i.first <= locations[0][dst] && locations[0][dst] <= i.second) {
      return dist + 1;
    } else
      return -1;
  }

  int parent(int v) { return locations[0][v]; }

  interval reachable_range(int v) { return reachable_from[v]; }

  int lca(int i, int j) {
    if (i == j) return i;
    if (depth[i] < depth[j]) swap(i, j);
    for (int layer = locations.size() - 1; layer >= 0; --layer) {
      if (locations[layer][i] != -1 && depth[locations[layer][i]] >= depth[j]) i = locations[layer][i];
    }
    if (i == j) return i;
    for (int layer = locations.size() - 1; layer >= 0; --layer) {
      if (locations[layer][i] != -1 && locations[layer][i] != locations[layer][j]) {
        i = locations[layer][i];
        j = locations[layer][j];
      }
    }
    return locations[0][i];
  }
};

Jumper fast, slow;

vector<int> H;

void init(int N, std::vector<int> _H) {
  H = _H;
  // impl detail so ng and pg are always defined on nodes that matter
  vector<int> ng = next_greater(H);
  reverse(H.begin(), H.end());
  vector<int> pg = next_greater(H);
  reverse(H.begin(), H.end());
  reverse(pg.begin(), pg.end());
  for (int &v : pg)
    v = (v == -1 ? -1 : N - 1 - v);

  vector<int> fast_tree(N, -1), slow_tree(N, -1);
  for (int i = 0; i < N; ++i) {
    if (ng[i] == -1 && pg[i] == -1)
      continue;
    else if (ng[i] == -1 || pg[i] == -1) {
      int par = max(ng[i], pg[i]);
      fast_tree[i] = slow_tree[i] = par;
    } else {
      pair<int, int> target1 = {H[ng[i]], ng[i]}, target2 = {H[pg[i]], pg[i]};
      if (target1 > target2)
        swap(target1, target2);
      fast_tree[i] = target2.second;
      slow_tree[i] = target1.second;
    }
    // cerr << "jump targets: " << fast_tree[i] << " " << slow_tree[i] << endl;
  }
  int max_idx = distance(begin(H), max_element(begin(H), end(H)));
  // get ranges for the slow tree
  vector slow_tree_init_ranges(N, pair{-1, -1});
  for (int i = 0; i < N; ++i) {
    slow_tree_init_ranges[i] = {min(i, slow_tree[i]), max(i, slow_tree[i])};
  }
  // cerr << " == processing slow tree " << endl;
  slow = Jumper(max_idx, slow_tree, slow_tree_init_ranges);

  // from traversal info on the slow tree, get ranges for the fast tree
  vector fast_tree_init_ranges(N, pair{-1, -1});
  for (int i = 0; i < N; ++i) {
    if (fast_tree[i] != -1) {
      pair ft_int{fast_tree[i], fast_tree[i]};
      pair slow_tree_int = get<2>(slow.last_before_overlapping(i, ft_int));
      fast_tree_init_ranges[i] = onion(slow_tree_int, ft_int);
    }
  }
  // cerr << " == processing fast tree " << endl;
  fast = Jumper(max_idx, fast_tree, fast_tree_init_ranges);
}

int brute_force_minimum_jumps(int A, int B, int C, int D) {
  vector<int> previ(H.size(), -1), nexti(H.size(), -1);
  for (int cur = 0; cur < H.size(); ++cur) {
    for (int i = cur - 1; i >= 0; --i)
      if (H[i] > H[cur]) {
        previ[cur] = i;
        break;
      }
    for (int j = cur + 1; j < H.size(); ++j)
      if (H[j] > H[cur]) {
        nexti[cur] = j;
        break;
      }
  }
  int ans = -1;
  for (int start = A; start <= B; ++start) {
    vector<int> dist(H.size(), -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      if (C <= cur && cur <= D) {
        ans = (ans == -1 ? dist[cur] : min(ans, dist[cur]));
      }
      int prev = previ[cur], next = nexti[cur];
      if (prev != -1 && dist[prev] == -1) {
        dist[prev] = dist[cur] + 1;
        q.push(prev);
      }
      if (next != -1 && dist[next] == -1) {
        dist[next] = dist[cur] + 1;
        q.push(next);
      }
    }
  }
  return ans;
}

int minimum_jumps_single_source(int src, int C, int D, interval possible_sources) {
  // cerr << "MJSS " << src << endl;
  if (possible_sources.first > src || possible_sources.second < src) return -1;
  // cerr << " starting from " << src << endl;
  int ans = -1;;
  auto consider = [&] (int v) {
    if (ans == -1 || (v != -1 && v < ans)) ans = v;
  };
  // take as many fast edges as possible before our path, traced along
  // the slow edges, hits {C, D}
  auto [v1, dist1, _] = fast.last_before_overlapping(src, {C, D});
  // cerr << " phase 1: " << v1 << " in " << dist1 << " jumps" << endl;
  int v1p = fast.parent(v1);
  if (C <= v1p && v1p <= D) {
    // case 1: another fast edge gets us there
    consider(dist1 + 1); 
  } else {
    // case 2: we get there using only slow edges
    auto [v2, dist2, __] = slow.last_before_overlapping(v1, {C, D});

    int pot_dst = slow.parent(v2);
    // cerr << " phase 2: " << v2 << " in " << dist2 << " jumps -> " << pot_dst << endl;
    if (C <= pot_dst && pot_dst <= D)
       consider(dist1 + dist2 + 1);

    // case 3: we need to take another fast edge
    // MAGIC CLAIM: This only happens O(sqrt(n)) times
    int further_dist = minimum_jumps_single_source(v1p, C, D, possible_sources);
    if (further_dist != -1) consider(further_dist + dist1 + 1);
  }
  // cerr << "MJSS " << src << " ret " << ans << endl;
  return ans;
}

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

  interval reachable_from_dst =
      slow.reachable_range(slow.lca(C, D));
  
  // cerr << "rfdst " << reachable_from_dst.first << " " << reachable_from_dst.second << endl;
  auto [realA, realB] = intersection({A, B}, reachable_from_dst);
  if (realA > realB) return -1;

  int src = slow.lca(realA, realB);

  return minimum_jumps_single_source(src, C, D, reachable_from_dst);
}

int minimum_jumps(int A, int B, int C, int D) {
  int ans = minimum_jumps_real(A, B, C, D);
  // int bans = brute_force_minimum_jumps(A, B, C, D);
  // cerr << "expected " << bans << " got " << ans << endl;
  // assert(ans == bans);
  return ans;
}

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