Submission #1131007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131007		Champ_Naman	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	2 ms	2120 KiB

skyscraper

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

const int N = 3e4, sq = 175;
vector<pair<int,int>> g[N];
int prnt[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, 1e9);

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;
      
      if(p < sq){
         prnt[b][p] = 1;
         continue;
      }

      for(int j=i-p, c = 1; j>=0; j -= p, c++) g[i].push_back({j, c});
      for(int j=i+p, c = 1; j<n; j += p, c++) g[i].push_back({j, c});
   }

   for(int i=0; i<n; i++){
      for(int p=0; p<sq; p++){
         if(!prnt[i][p]) continue;

         for(int j=i-p, c = 1; j>=0; j -= p, c++){
            g[i].push_back({j, c});
            if(prnt[j][p]) break;
         }
         for(int j=i+p, c = 1; j<n; j += p, c++){
            g[i].push_back({j, c});
            if(prnt[j][p]) break;
         }
      }
   }

   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] == 1e9 ? -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: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43