Submission #1009761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009761		asdfgrace	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	552 ms	53616 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
can jump only multiples of 1 number
get from p0 to p1
can only jump if 0 or it was passed to you
everyone will only have it once?
can add o(n^2) edges and dijkstra

idea:
nsqrtn
from each node
for each p[i] > sqrt(n), dijkstra to all the nodes that work
also for each node
keep sqrtn distances that you can use to travel to nearby nodes
for each node, keep the overall best dist, but also allow jump
values < sqrt(n) that the node itself doesn't have to visit the node
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  int s = (int) sqrt(n);
  vector<int> a(m), b(m);
  vector<vector<array<int, 2>>> edges(n);
  vector<vector<bool>> jump(n, vector<bool>(s, false));
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    if (b[i] >= s) {
      for (int j = a[i] + b[i]; j < n; j += b[i]) {
        edges[a[i]].push_back({j, (j - a[i]) / b[i]});
      }
      for (int j = a[i] - b[i]; j >= 0; j -= b[i]) {
        edges[a[i]].push_back({j, (a[i] - j) / b[i]});
      }
    } else {
      jump[a[i]][b[i]] = true;
    }
  }
  vector<vector<int>> dist(n, vector<int>(s, 1e9));
  dist[a[0]][0] = 0;
  vector<bool> vis(n, false);
  priority_queue<array<int, 3>> q;
  q.push({0, a[0], 0});
  while (q.size()) {
    int d = -q.top()[0], node = q.top()[1], jsz = q.top()[2];
    q.pop();
    if (d != dist[node][jsz]) continue;
    if (!vis[node]) {
      for (auto [next, wt] : edges[node]) {
        if (d + wt < dist[next][0]) {
          dist[next][0] = d + wt;
          q.push({-dist[next][0], next, 0});
        }
      }
      for (int nj = 1; nj < s; nj++) {
        if (jump[node][nj]) {
          if (node + nj < n && d + 1 < dist[node + nj][nj]) {
            dist[node + nj][nj] = d + 1;
            q.push({-dist[node + nj][nj], node + nj, nj});
          }
          if (node - nj >= 0 && d + 1 < dist[node - nj][nj]) {
            dist[node - nj][nj] = d + 1;
            q.push({-dist[node - nj][nj], node - nj, nj});
          }
        }
      }
      vis[node] = true;
    }
    if (jsz != 0) {
      if (node + jsz < n && d + 1 < dist[node + jsz][jsz]) {
        dist[node + jsz][jsz] = d + 1;
        q.push({-dist[node + jsz][jsz], node + jsz, jsz});
      }
      if (node - jsz >= 0 && d + 1 < dist[node - jsz][jsz]) {
        dist[node - jsz][jsz] = d + 1;
        q.push({-dist[node - jsz][jsz], node - jsz, jsz});
      }
    }
  }
  int mn = 1e9;
  for (int i = 0; i < s; i++) {
    mn = min(mn, dist[a[1]][i]);
  }
  cout << (mn == 1e9 ? -1 : mn) << '\n';
}

/*
any observations help

check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER

NEVER GIVE UP
*/

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