Submission #652776

#	Time	Username	Problem	Language	Result	Execution time	Memory
652776		alvinpiter	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	120 ms	33140 KiB

skyscraper

/*
5 3
0 2
1 1
4 1
*/

#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 2000
#define MAXP 2000

int n, m, startPosition, startPower, endPosition, dist[MAXN + 3][MAXP + 3];
vector<int> dogesAtPosition[MAXN + 3];

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int b, p;
    cin >> b >> p;

    if (i == 0) {
      startPosition = b;
      startPower = p;
    }

    if (i == 1) {
      endPosition = b;
    }

    dogesAtPosition[b].push_back(p);
  }

  for (int i = 0; i < n; i++) {
    sort(dogesAtPosition[i].begin(), dogesAtPosition[i].end());
    dogesAtPosition[i].erase(unique(dogesAtPosition[i].begin(), dogesAtPosition[i].end()), dogesAtPosition[i].end());
  }

  for (int i = 0; i < n; i++) {
    for (int p = 1; p <= MAXP; p++) {
      dist[i][p] = INF;
    }
  }
  dist[startPosition][startPower] = 0;

  priority_queue<pair<int, pair<int, int> > > pq;
  pq.push({-dist[startPosition][startPower], {startPosition, startPower}});

  while (!pq.empty()) {
    auto [d, state] = pq.top(); pq.pop();
    auto [position, power] = state;

    d *= -1; // Hacky
    if (d > dist[position][power]) {
      continue;
    }

    // Pass to other doge
    for (auto p: dogesAtPosition[position]) {
      if (dist[position][p] > dist[position][power]) {
        dist[position][p] = dist[position][power];
        pq.push({-dist[position][p], {position, p}});
      }
    }

    // Jump
    for (int direction = -1; direction <= 1; direction += 2) {
      int newPosition = position + direction * power;
      if (newPosition >= 0 && newPosition < n && dist[newPosition][power] > dist[position][power] + 1) {
        dist[newPosition][power] = dist[position][power] + 1;
        pq.push({-dist[newPosition][power], {newPosition, power}});
      }
    }
  }

  int ans = INF;
  for (int p = 1; p <= MAXP; p++) {
    ans = min(ans, dist[endPosition][p]);
  }

  if (ans < INF) {
    cout << ans << endl;
  } else {
    cout << -1 << endl;
  }
}

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