제출 #922376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922376		Aiperiii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	172 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);
   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;
         }
      }
   }
   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,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";
}

/*
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