Submission #970899

#	Time	Username	Problem	Language	Result	Execution time	Memory
970899		kilkuwu	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	60 ms	5840 KiB

skyscraper

#include <bits/stdc++.h>

#define nl '\n'

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

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];

    doges[B[i]].insert(P[i]);
  }

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

  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 (int p : doges[u]) {
        for (int w = 1; u + w * p < N; w++) {
          int to = u + w * p; 
          auto dd = dp[u] + w; 
          if (dd < dp[to]) {
            dp[to] = dd;
            pq.emplace(-dp[to], to);
          }

          if (doges[to].find(p) != doges[to].end()) break;
        }

        for (int w = 1; u - w * p >= 0; w++) {
          int to = u - w * p;

          auto dd = dp[u] + w; 
          if (dd < dp[to]) {
            dp[to] = dd;
            pq.emplace(-dp[to], to);
          }

          if (doges[to].find(p) != doges[to].end()) break;
        }
      }
    }

    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: 43 / 43