Submission #652966

#	Time	Username	Problem	Language	Result	Execution time	Memory
652966		alvinpiter	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	959 ms	24644 KiB

skyscraper

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

#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 30000
#define THRESHOLD 180

int n, m, startPosition, endPosition, dist[MAXN + 3][THRESHOLD + 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;
    }

    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 = 0; p <= THRESHOLD; p++) {
      dist[i][p] = INF;
    }
  }
  dist[startPosition][0] = 0;

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

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

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

    if (power == 0) {
      for (auto newPower: dogesAtPosition[position]) {
        if (newPower <= THRESHOLD) {
          if (dist[position][newPower] > dist[position][power]) {
            dist[position][newPower] = dist[position][power];
            pq.push({-dist[position][newPower], {position, newPower}});
          }
        } else {
          for (int direction = -1; direction <= 1; direction += 2) {
            for (int numJumps = 1; ; numJumps++) {
              int newPosition = position + direction * newPower * numJumps;
              if (newPosition < 0 || newPosition >= n) {
                break;
              }

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

          if (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 = 0; p <= THRESHOLD; 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: 43 / 43