Submission #922392

#	Time	Username	Problem	Language	Result	Execution time	Memory
922392		Aiperiii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	285 ms	121524 KiB

skyscraper

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int n,m;
   cin>>n>>m;
   vector <int> b(m),p(m);
   set <int> s[n];
   for(int i=0;i<m;i++){
      cin>>b[i]>>p[i];
      s[b[i]].insert(p[i]);
   }
   vector <pair <int,int> > g[n];
   for(int i=0;i<n;i++){
      for(auto x : s[i]){
         int y=i+x,cnt=1;
         if(y<n){
            g[i].pb({y,1});
         }
         while(y+x<n){
            cnt++;
            if(s[y].find(x)==s[y].end()){
               g[i].pb({y+x,cnt});
               y+=x;
            }else break;
         }
         y=i-x;cnt=1;
         if(y>=0)g[i].pb({y,1});
         while(y-x>=0){
            cnt++;
            if(s[y].find(x)==s[y].end()){
               g[i].pb({y-x,cnt});
               y-=x;
            }else break;
         }
      }
   }
   set <pair <int,int> > st;
   vector <int> d(n,1e12);
   st.insert({0,b[0]});
   d[b[0]]=0;
   while(!st.empty()){
      int v=st.begin()->second;
      //cout<<v<<" "<<d[v]<<"\n";
      st.erase(st.begin());
      for(auto to : g[v]){
         if(d[to.ff]>d[v]+to.ss){
            st.erase({d[to.ff],to.ff});
            d[to.ff]=d[v]+to.ss;
            st.insert({d[to.ff],to.ff});
         }
      }
   }
   if(d[b[1]]==1e12)d[b[1]]=-1;
   cout<<d[b[1]]<<"\n";
}

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