Submission #1130963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130963		Champ_Naman	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	467 ms	327680 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

const int N = 3e4, sq = 175;
vector<pair<int,int>> g[N];
int power[N][sq];

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> vis(N, 0);
vector<int> dist(N, 1e18);

inline void solve(){
   int n, m, st, dt;
   cin>>n>>m;

   for(int i=0; i<m; i++){
      int b, p;
      cin>>b>>p;
      if(i == 0) st = b;
      if(i == 1) dt = b;
      
      for(int j=b-p, c = 1; j>=0; j -= p, c++){
         g[b].push_back({j, c});
         if(p < sq and power[j][p]) break;
      }
      for(int j=b+p, c = 1; j<n; j += p, c++){
         g[b].push_back({j, c});
         if(p < sq and power[j][p]) break;
      }

      if(p < sq) power[b][p] = 1;
   }

   pq.push({0, st});
   dist[st] = 0;

   while(!pq.empty()){
      auto [d, v] = pq.top();
      pq.pop();

      if(vis[v]) continue;
      vis[v] = 1;

      for(auto [ch, w] : g[v]){
         if(d + w < dist[ch]){
            dist[ch] = d + w;
            pq.push({dist[ch], ch});
         }
      }
   }

   cout<<(dist[dt] == 1e18 ? -1 : dist[dt])<<nl;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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