Submission #922313

#	Time	Username	Problem	Language	Result	Execution time	Memory
922313		Aiperiii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	186 ms	262144 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);
   for(int i=0;i<m;i++){
      cin>>b[i]>>p[i];
   }
   vector <pair <int,int> > g[n];
   for(int i=0;i<m;i++){
      int x=b[i],cnt=0;
      while(x+p[i]<n){
         x+=p[i];cnt++;
         g[b[i]].pb({x,cnt});
      }
      x=b[i];cnt=0;
      while(x-p[i]>=0){
         x-=p[i];cnt++;
         g[b[i]].pb({x,cnt});
      }
   }

   set <pair <int,int> > st;
   vector <int> d(n,1e18);
   st.insert({0,b[0]});
   d[b[0]]=0;
   while(!st.empty()){
      int v=st.begin()->second;
      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]]==1e18)d[b[1]]=-1;
   cout<<d[b[1]]<<"\n";
}

/*
 5 3
 0 2
 1 1
 4 1
 */

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