Submission #1195434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195434		Sarvar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n,m;
  if(!(cin>>n>>m))return 0;
  vector<int>b(m),p(m);
  vector<vector<int>> at(n);
  for(int i=0;i<m;i++){
    cin>>b[i]>>p[i];
    at[b[i]].push_back(i);
  }
  const ll INF = LLONG_MAX/4;
  vector<ll> dist(m,INF);
  vector<char> vis(m,0);
  dist[0]=0;
  priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
  pq.push({0,0});
  while(!pq.empty()){ 
    auto [d,i] = pq.top(); pq.pop();
    if(vis[i]) continue;
    vis[i]=1;
    if(i==1) break;
    int bi=b[i], pi=p[i];
    // jump right
    for(ll k=1, x=bi+pi; x<n; x+=pi, ++k){
      for(int j: at[x]) if(!vis[j] && dist[j] > d + k){ dist[j] = d + k; pq.push({dist[j], j}); }
    }
    // jump left
    for(ll k=1, x=bi-pi; x>=0; x-=pi, ++k){
      for(int j: at[x]) if(!vis[j] && dist[j] > d + k){ dist[j] = d + k; pq.push({dist[j], j}); }
    }
  }
  ll ans = dist[1];
  if(ans==INF) cout<<-1;
  else cout<<ans;
  return 0;
}

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