Submission #874530

#	Time	Username	Problem	Language	Result	Execution time	Memory
874530		chadmod	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	591 ms	3880 KiB

skyscraper

/**
 *    author:  NimaAryan
 *    created: 2023-11-17 08:21:07
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template <typename T = i64>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T = i64>
using max_heap = priority_queue<T, vector<T>, less<T>>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M;
  cin >> N >> M;

  vector<int> B(M), P(M);
  for (int i = 0; i < M; ++i) {
    cin >> B[i] >> P[i];
  }

  vector<vector<int>> at(N);
  for (int i = 0; i < M; ++i) {
    at[B[i]].push_back(P[i]);
  }

  constexpr int inf = numeric_limits<int>::max();

  vector<int> dist(N, inf);
  vector<bool> vis(N);

  min_heap<pair<int, int>> h;
  auto add = [&](int v, int c) {
    if (c < dist[v]) {
      h.emplace(dist[v] = c, v);
    }
  };
  add(B[0], 0);

  while (!h.empty()) {
    auto [cd, v] = h.top();
    h.pop();
    if (cd > dist[v]) {
      continue;
    }
    vis[v] = true;
    for (int p : at[v]) {
      for (int t = 1; v + t * p < N; ++t) {
        int u = v + t * p;
        add(u, cd + t);
      }
      for (int t = 1; v - t * p >= 0; ++t) {
        int u = v - t * p;
        add(u, cd + t);
      }
    }
  }

  cout << (vis[B[1]] ? dist[B[1]] : -1) << "\n";

  return 0;
}

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