Submission #1275657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275657		behrad	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	544 ms	6060 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 3e4+4, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, m, B[maxn], P[maxn];
ll dis[maxn];
vector<int> mv[maxn];

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> m;
  for (int i = 1 ; i <= m ; i ++) {
    cin >> B[i] >> P[i];
    mv[B[i]].pb(P[i]);
  }
  for (int i = 0 ; i < n ; i ++) {
    sort(mv[i].begin(), mv[i].end());
    mv[i].resize(unique(mv[i].begin(), mv[i].end()) - mv[i].begin());

    dis[i] = inf;
  }
  
  priority_queue<pii, vector<pii>, greater<pii>> q;
  dis[B[1]] = 0;
  q.push({0, B[1]});
  while (q.size()) {
    auto [d, v] = q.top(); q.pop();
    if (d > dis[v]) continue;

    for (int x : mv[v]) {
      for (int u = v + x, k = 1 ; u < n ; u += x, k ++) {
        if (dis[u] > dis[v] + k) {
          dis[u] = dis[v] + k;
          q.push({dis[u], u});
        }
      }
      for (int u = v - x, k = 1 ; u >= 0 ; u -= x, k ++) {
        if (dis[u] > dis[v] + k) {
          dis[u] = dis[v] + k;
          q.push({dis[u], u});
        }
      }
    }
  }
  
  cout << (dis[B[2]] == inf ? -1 : dis[B[2]]) << nl;
}

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