Submission #970732

#	Time	Username	Problem	Language	Result	Execution time	Memory
970732		kilkuwu	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	401 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>

#define nl '\n'

const int mxN = 30006;
std::set<std::pair<int, int>> doges[mxN];
int B[mxN], P[mxN];
int N, M;

std::vector<std::pair<int, int>> adj[mxN];

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

  std::cin >> N >> M;
  
  for (int i = 0; i < M; i++) {
    std::cin >> B[i] >> P[i];

    auto it = doges[B[i]].lower_bound({P[i], -1});

    if (it == doges[B[i]].end() || it->first != P[i]) {
      doges[B[i]].insert({P[i], i});
    }
  }

  if (B[0] == B[1]) {
    std::cout << 0 << nl;
    return 0;
  }

  for (int i = 0; i < N; i++) {
    for (auto [power, id] : doges[i]) {
      for (int w = 1; i + w * power < N; w++) {
        int to = i + w * power;
        auto it = doges[to].find({power, -1});
        if (it != doges[to].end() && it->first == power) {
          break;
        }
        adj[i].emplace_back(w, to);
      } 
      for (int w = 1; i - w * power >= 0; w++) {
        int to = i - w * power;
        auto it = doges[to].find({power, -1});
        if (it != doges[to].end() && it->first == power) {
          break;
        }
        adj[i].emplace_back(w, to);
      }
    } 
  }

  auto dijkstra = [&](int s) -> int {
    std::priority_queue<std::pair<int, int>> pq;
    std::vector<int> dp(N, 1e9);
    dp[s] = 0;

    pq.push({0, s});
    while (pq.size()) {
      auto [d, u] = pq.top();
      d = -d;
      pq.pop();
      if (dp[u] < d) continue;

      for (auto [w, v] : adj[u]) {
        if (dp[v] > d + w) {
          dp[v] = d + w;
          pq.emplace(-dp[v], v);
        } 
      }
    }

    return dp[B[1]] < 1e9 ? dp[B[1]] : -1;
  };

  std::cout << dijkstra(B[0]) << nl;
}

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