제출 #550139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550139		Soumya1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	923 ms	55832 KiB

skyscraper

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 30'000;
vector<int> all[mxN], init[mxN], l[mxN];
vector<int> dist[mxN];
bool vis[mxN];
int idx(int i, int j) {
  if (j < 200) return j;
  return 200 + lower_bound(all[i].begin(), all[i].end(), j) - all[i].begin();
}
void testCase() {
  int n, m;
  cin >> n >> m;
  vector<int> v;
  while (m--) {
    int b, p;
    cin >> b >> p;
    v.push_back(b);
    init[b].push_back(p);
    l[b % p].push_back(p);
  }
  for (int i = 0; i < n; i++) {
    sort(l[i].begin(), l[i].end());
    sort(init[i].begin(), init[i].end());
    init[i].erase(unique(init[i].begin(), init[i].end()), init[i].end());
    l[i].erase(unique(l[i].begin(), l[i].end()), l[i].end());
  }
  for (int i = 0; i < n; i++) {
    for (int j : l[i]) {
      if (j < 200) continue;
      for (int k = i; k < n; k += j) {
        all[k].push_back(j);
      }
    }
    sort(all[i].begin(), all[i].end());
    dist[i].assign(all[i].size() + 200, 1e9);
  }
  queue<tuple<int, int, int>> q;
  for (auto p : init[v[0]]) {
    vis[v[0]] = true;
    int vv = idx(v[0], p);
    q.push({v[0], p, vv});
    dist[v[0]][vv] = 0;
  }
  while (!q.empty()) {
    auto [u, p, id] = q.front();
    q.pop();
    int i;
    if (u + p < n) i = idx(u + p, p);
    if (u + p < n && dist[u + p][i] == 1e9) {
      dist[u + p][i] = dist[u][id] + 1;
      q.push({u + p, p, i});
    }
    if (u + p < n && !vis[u + p]) {
      vis[u + p] = true;
      for (int pp : init[u + p]) {
        i = idx(u + p, pp);
        if (dist[u + p][i] == 1e9) {
          dist[u + p][i] = dist[u][id] + 1;
          q.push({u + p, pp, i});
        }
      }
    }
    if (u - p >= 0) i = idx(u - p, p);
    if (u - p >= 0 && dist[u - p][i] == 1e9) {
      dist[u - p][i] = dist[u][id] + 1;
      q.push({u - p, p, i});
    }
    if (u - p >= 0 && !vis[u - p]) {
      vis[u - p] = true;
      for (int pp : init[u - p]) {
        i = idx(u - p, pp);
        if (dist[u - p][i] == 1e9) {
          dist[u - p][i] = dist[u][id] + 1;
          q.push({u - p, pp, i});
        }
      }
    }
  }
  int ans = *min_element(dist[v[1]].begin(), dist[v[1]].end());
  cout << (ans == 1e9 ? -1 : ans) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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