Submission #1130762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130762		Hamed_Ghaffari	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	115 ms	65592 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back
#define Mp make_pair
#define all(x) x.begin(), x.end()

using ll = long long;
using pii = pair<int, int>;

const int  INF = 1e9;
const int MXN = 3e4+4;

vector<pii> g[MXN];
int dis[MXN];
int n, m, B[MXN], P[MXN];
set<int> st[MXN];
inline void add_edge(int u, int v, int w) {
  g[u].pb(pii(v,w));
}
inline int dijkstra(int s, int t) {
  fill(dis, dis+n, INF);
  dis[s] = 0;
  priority_queue<pii> pq;
  pq.push(pii(0, s));
  while(!pq.empty()) {
    int d = -pq.top().X, v = pq.top().Y;
    pq.pop();
    if(d!=dis[v]) continue;
    for(auto [u, w] : g[v])
      if(dis[u]>d+w) 
        pq.push(pii(-(dis[u]=d+w), u));
  }
  return dis[t];
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    cin >> B[i] >> P[i];
    st[B[i]].insert(P[i]);
  }
  for(int i=0; i<n; i++)
    for(int p : st[i]) {
      int cost = 0;
      for(int j=i+p; j<n; j+=p) {
        add_edge(i, j, ++cost);
        if(st[j].find(p) != st[j].end()) break;
      }
      cost = 0;
      for(int j=i-p; j>=0; j-=p) {
        add_edge(i, j, ++cost);
        if(st[j].find(p) != st[j].end()) break;
      }
    }
  int ans = dijkstra(B[0], B[1]);
  if(ans == INF) ans = -1;
  cout << ans << '\n';
  return 0;
}

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