Submission #1130753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130753		Hamed_Ghaffari	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	3 ms	3652 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;

int N;
vector<vector<pair<int, bool>>> g;
vector<int> dis;
vector<pair<pii, bool>> E;
inline void add_edge(int u, int v, bool w) {
  E.pb(Mp(pii(u,v), w));
}
inline int BFS01(int s, int t) {
  g.resize(N);
  for(auto e : E)
    g[e.X.X].pb(Mp(e.X.Y, e.Y));
  dis.resize(N, INF);
  dis[s] = 0;
  queue<int> q[2];
  int z=0, v;
  q[z].push(s);
  while(!q[0].empty() || !q[1].empty()) {
    if(q[z].empty()) z ^= 1;
    v = q[z].front();
    q[z].pop();
    for(auto [u, w] : g[v])
      if(dis[u]>dis[v]+w) {
        dis[u] = dis[v]+w;
        if(w) q[z^1].push(u);
        else q[z].push(u);
      }
  }
  return dis[t];
}

const int MXN = 3e4+4;
int n, m, B[MXN], P[MXN];
unordered_map<int, int> st[MXN];
unordered_map<int, bool> chk[MXN];

inline int id(int i, int p) {
  if(!st[i][p]) st[i][p]=N++;
  return st[i][p];
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> m;
  N=n;
  for(int i=0; i<m; i++) {
    cin >> B[i] >> P[i];
    int b = B[i]%P[i];
    if(!chk[b][P[i]]) {
      for(int j=b; j<n; j+=P[i]) {
        add_edge(id(j, P[i]), j, 0);
        if(j+P[i]<n)
          add_edge(id(j, P[i]), id(j+P[i], P[i]), 1),
          add_edge(id(j+P[i], P[i]), id(j, P[i]), 1);
      }
      chk[b][P[i]]=1;
    }
    add_edge(B[i], id(B[i], P[i]), 0);
  }
  cout << SZ(E) << '\n';
  int ans = BFS01(id(B[0], P[0]), id(B[1],P[1]));
  if(ans == INF) ans = -1;
  cout << ans << '\n';
  return 0;
}

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