Submission #984104

#	Time	Username	Problem	Language	Result	Execution time	Memory
984104		Marcus	Rainforest Jumps (APIO21_jumps)	C++17	21 / 100	268 ms	48720 KiB

jumps

#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> h;
const int INF = 2e6;
vector<vector<int>> adj(2000);
vector<vector<int>> dist(2000, vector<int>(2000, INF));
int powtwo = (int)pow(2, __lg(2000) + !!(2000 & (2000-1)));

void bfs(int x)
{
	queue<int> q;
    vector<bool> visited(n);
    int start = x;
	visited[start] = true;
    dist[start][start] = 0;
    q.push(start);
    while (!q.empty()) {
        int s = q.front(); q.pop();
        for (auto u : adj[s]) {
            if (visited[u]) continue;
            visited[u] = true;
            dist[start][u] = dist[start][s]+1;
            q.push(u);
        }
    }
}

struct SegmentTree {
  vector<int> t;

  SegmentTree(int power) : t(2*power) {}
  
  void build(vector<int>& a, int v, int tl, int tr) {
      if (tl == tr) {
          if (tl < (int)a.size()) t[v] = a[tl];
          else t[v] = INF;
      } else {
          int tm = (tl + tr) / 2;
          build(a, v*2, tl, tm);
          build(a, v*2+1, tm+1, tr);
          t[v] = min(t[v*2], t[v*2+1]);
      }
  }
  
  int query(int v, int tl, int tr, int l, int r) {
      if (l > r) return INF;
      if (l == tl && r == tr) return t[v];
      int tm = (tl + tr) / 2;
      return min(query(v*2, tl, tm, l, min(r, tm)), 
                     query(v*2+1, tm+1, tr, max(l, tm+1), r));
  }
};

vector<SegmentTree> segdist;
 
void init(int N, std::vector<int> H) {
    n = N;
    for (auto u: H) {h.push_back(u);}
    h.shrink_to_fit();

    for (int i=0; i<n; i++)
    {
        for (int j=i; j<n; j++)
        {
            if (h[i] < h[j]) {adj[i].push_back(j); break;};
        }
        for (int j=i; j>=0; j--)
        {
            if (h[i] < h[j]) {adj[i].push_back(j); break;};
        }
    }

    for (int i=0; i<n; i++) {bfs(i);}

    for (int i=0; i<n; i++)
    {
        SegmentTree segtree(powtwo); 
        segtree.build(dist[i], 1, 0, powtwo-1);
        segdist.push_back(segtree);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
  int answer = INF;
  for (int i=A; i<=B; i++)
  {
    answer = min(answer, segdist[i].query(1, 0, powtwo-1, C, D));
  }
  return (answer >= INF ? -1 : answer);
}

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