Submission #258206

#	Time	Username	Problem	Language	Result	Execution time	Memory
258206		EntityIT	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	883 ms	24952 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_skyscrapers, n_doges; cin >> n_skyscrapers >> n_doges;
  vec<int, 2> steps_skyscrapers(n_skyscrapers);
  int source, target;
  for (int i = 0; i < n_doges; ++i) {
    int skyscraper, step; cin >> skyscraper >> step;
    steps_skyscrapers[skyscraper].emplace_back(step);
    if (!i) {
      source = skyscraper;
    } else if (i == 1) {
      target = skyscraper;
    }
  }
  for (auto& doges : steps_skyscrapers) {
    sort(ALL(doges));
    doges.erase(unique(ALL(doges)), doges.end());
  }

  int const magic = static_cast<int>(sqrt(n_skyscrapers)) + 1;

  vec<int, 2> f(n_skyscrapers, magic + 1, numeric_limits<int>::max());
  f[source].back() = 0;
  priority_queue<tuple<int, int, int>> pq;
  pq.emplace(0, source, magic);

  while (SZ(pq)) {
    int current_f, skyscraper, step; tie(current_f, skyscraper, step) = pq.top(); pq.pop();
    current_f = -current_f;

    if (current_f != f[skyscraper][step]) {
      continue;
    }

    if (step < magic) {
      if (skyscraper + step < n_skyscrapers && Minimize(f[skyscraper + step][step], current_f + 1)) {
        pq.emplace(-f[skyscraper + step][step], skyscraper + step, step);
      }
      if (skyscraper - step >= 0 && Minimize(f[skyscraper - step][step], current_f + 1)) {
        pq.emplace(-f[skyscraper - step][step], skyscraper - step, step);
      }
      if (Minimize(f[skyscraper][magic], current_f)) {
        pq.emplace(-f[skyscraper][magic], skyscraper, magic);
      }
    } else {
      for (auto& new_step : steps_skyscrapers[skyscraper]) {
        if (new_step < magic) {
          if (Minimize(f[skyscraper][new_step], current_f)) {
            pq.emplace(-f[skyscraper][new_step], skyscraper, new_step);
          }
        } else {
          for (int next_skyscraper = skyscraper + new_step, next_distance = current_f + 1; next_skyscraper < n_skyscrapers; next_skyscraper += new_step, ++next_distance) {
            if (Minimize(f[next_skyscraper][magic], next_distance)) {
              pq.emplace(-f[next_skyscraper][magic], next_skyscraper, magic);
            }
          }
          for (int next_skyscraper = skyscraper - new_step, next_distance = current_f + 1; next_skyscraper >= 0; next_skyscraper -= new_step, ++next_distance) {
            if (Minimize(f[next_skyscraper][magic], next_distance)) {
              pq.emplace(-f[next_skyscraper][magic], next_skyscraper, magic);
            }
          }
        }
      }
    }
  }

  int answer = *min_element(ALL(f[target]));
  cout << (answer < numeric_limits<int>::max() ? answer : -1) << '\n';

  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:96:41: warning: 'target' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int answer = *min_element(ALL(f[target]));
                                         ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43