Submission #1130740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130740		Champ_Naman	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	1 ms	584 KiB

skyscraper

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

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

   vector<pair<int,int>> g[n];
   set<int> unused[n];
   for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(i != j) unused[i].insert(j);

   for(int i=0; i<m; i++){
      int b, p;
      cin>>b>>p;
      if(i == 0) st = b;
      if(i == 1) dt = b;
      
      for(auto it = unused[b].begin(); it != unused[b].end();){
         auto cr = it++;
         int x = *cr;
         if(abs(x - b) % p == 0) g[b].push_back({x, abs(x - b)/p});
         
         unused[b].erase(cr);
      }
   }

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

   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: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43