Submission #1193759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193759		emad234	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	210 ms	111176 KiB

skyscraper

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 4e6 + 5;
using namespace std;
vector<pii>v[mxN];
int pos[2];
int dist[mxN];
bool operator<(pair<int,int>a,pair<int,int>b){
  return a.S > b.S;
}
int n,m;
int conv(int q,int p){
  return p * n + q;
}
signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >>n>>m;
  int buck = 175;
  for(int i = 0;i < m;i++){
    int q,p;
    cin >>q>>p;
    if(i < 2) pos[i] = q;
    if(p <= buck){
      v[conv(q,0)].push_back({conv(q,p),0});
    }else{
      int cnt = 1;
      for(int j = q - p;j >= 0;j -= p){
        v[conv(q,0)].push_back({conv(j,0),cnt});
        cnt++;
      }
      cnt = 1;
      for(int j = q + p;j < n;j += p){
        v[conv(q,0)].push_back({conv(j,0),cnt});
        cnt++;
      }
    }
  }
  for(int i = 0;i < n;i++){
    for(int p = 0;p <= buck;p++){
      dist[conv(i,p)] = 1e9;
    }
  }
  dist[pos[0]] = 0;
  priority_queue<pair<int,int>>q;
  q.push({pos[0],0});
  while(q.size()){
    auto u = q.top();
    // cout<<u.F.q<<' '<<u.F.p<<' '<<u.S<<'\n';
    q.pop();
    if(dist[u.F] < u.S) continue;
    for(auto x : v[u.F]){
      if(dist[x.F] > u.S + x.S){
        dist[x.F] = u.S + x.S;
        q.push({x.F,dist[x.F]});
      }
    }
    pii x;
    if(u.F >= n){
      x = {u.F + u.F / n,1};
      if(x.F / n == u.F / n && dist[x.F] > u.S + x.S){
        dist[x.F] = u.S + x.S;
        q.push({x.F,dist[x.F]});
      }
      x = {u.F - u.F / n,1};
      if(x.F / n == u.F / n && dist[x.F] > u.S + x.S){
        dist[x.F] = u.S + x.S;
        q.push({x.F,dist[x.F]});
      }
      x = {u.F % n,0};
      if(dist[x.F] > u.S + x.S){
        dist[x.F] = u.S + x.S;
        q.push({x.F,dist[x.F]});
      }
    }
  }
  cout<<(dist[pos[1]] == 1e9 ? -1 : dist[pos[1]]);
}

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