Submission #549621

#	Time	Username	Problem	Language	Result	Execution time	Memory
549621		Soumya1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	5 ms	4664 KiB

skyscraper

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 30'000;
set<int> l[mxN], init[mxN];
vector<int> all[mxN];
vector<int> dist[mxN];
bool vis[mxN];
int idx(int i, int j) {
  return 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].insert(p);
    l[b % p].insert(p);
  }
  for (int i = 0; i < n; i++) {
    for (int j : l[i]) {
      if (i + j < n) l[i + j].insert(j);
    }
    all[i] = vector<int> (l[i].begin(), l[i].end());
    dist[i].assign(all[i].size(), 1e9);
  }
  deque<pair<int, int>> q;
  for (auto p : init[v[0]]) {
    q.push_back({v[0], p});
    dist[v[0]][idx(0, p)] = 0;
  }
  while (!q.empty()) {
    auto [u, p] = q.front();
    // debug(u, p, dist[u][idx(u, p)]);
    q.pop_front();
    if (u + p < n && dist[u + p][idx(u + p, p)] == 1e9) {
      dist[u + p][idx(u + p, p)] = dist[u][idx(u, p)] + 1;
      q.push_front({u + p, p});
    }
    if (u - p >= 0 && dist[u - p][idx(u - p, p)] == 1e9) {
      dist[u - p][idx(u - p, p)] = dist[u][idx(u, p)] + 1;
      q.push_front({u - p, p});
    }
    if (vis[u]) continue;
    int j = idx(u, p);
    for (int pp : init[u]) {
      if (dist[u][idx(u, pp)] == 1e9) {
        dist[u][idx(u, pp)] = dist[u][j];
        q.push_back({u, pp});
      }
    }
    vis[u] = true;
  }
  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: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43