제출 #1130758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130758		Hamed_Ghaffari	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	914 ms	310716 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

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

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

vector<pii> g[MX];
int dis[MX];
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+MX, 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];
}

int n, m, sq, B[MXN], P[MXN];

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> m;
  sq=1; while(sq*(sq++)<=n); sq--;
  for(int i=0; i<n; i++)
    for(int p=1; p<=sq; p++) {
      if(i-p>=0) {
        add_edge(p*n+i, p*n+i-p, 1);
        add_edge(p*n+i, i-p, 1);
      }
      if(i+p<n) {
        add_edge(p*n+i, p*n+i+p, 1);
        add_edge(p*n+i, i+p, 1);
      }
    }
  for(int i=0; i<m; i++) {
    cin >> B[i] >> P[i];
    if(P[i]<=sq) add_edge(B[i], P[i]*n+B[i], 0);
    else {
      for(int j=B[i]%P[i]; j<n; j+=P[i])
        if(i^j)
          add_edge(B[i], j, abs(B[i]-j)/P[i]);
    }
  }
  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: 0 / 43