제출 #549630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549630		Soumya1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1090 ms	51276 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++) {
    all[i] = vector<int> (l[i].begin(), l[i].end());
  }
  for (int i = 0; i < n; i++) {
    for (int j : all[i]) {
      if (i + j < n) all[i + j].push_back(j);
    }
    sort(all[i].begin(), all[i].end());
    all[i].erase(unique(all[i].begin(), all[i].end()), all[i].end());
    dist[i].assign(all[i].size(), 1e9);
  }
  queue<pair<int, int>> q;
  for (auto p : init[v[0]]) {
    vis[v[0]] = true;
    q.push({v[0], p});
    dist[v[0]][idx(v[0], p)] = 0;
  }
  while (!q.empty()) {
    auto [u, p] = q.front();
    int id = idx(u, p);
    q.pop();
    if (u + p < n && dist[u + p][idx(u + p, p)] == 1e9) {
      dist[u + p][idx(u + p, p)] = dist[u][id] + 1;
      q.push({u + p, p});
    }
    if (u + p < n && !vis[u + p]) {
      vis[u + p] = true;
      for (int pp : init[u + p]) {
        int i = idx(u + p, pp);
        if (dist[u + p][i] == 1e9) {
          dist[u + p][i] = dist[u][id] + 1;
          q.push({u + p, pp});
        }
      }
    }
    if (u - p >= 0 && dist[u - p][idx(u - p, p)] == 1e9) {
      dist[u - p][idx(u - p, p)] = dist[u][id] + 1;
      q.push({u - p, p});
    }
    if (u - p >= 0 && !vis[u - p]) {
      vis[u - p] = true;
      for (int pp : init[u - p]) {
        int i = idx(u - p, pp);
        if (dist[u - p][i] == 1e9) {
          dist[u - p][i] = dist[u][id] + 1;
          q.push({u - p, pp});
        }
      }
    }
  }
  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: 0 / 43