Submission #243947

#	Time	Username	Problem	Language	Result	Execution time	Memory
243947		NaimSS	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	716 ms	229492 KiB

skyscraper

        #include <bits/stdc++.h>
        #define ld long double
        #define endl "\n"
        #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        #define pb(x) push_back(x)
        #define mp(a,b) make_pair(a,b)
        #define ms(v,x) memset(v,x,sizeof(v))
        #define all(v) v.begin(),v.end()
        #define ff first
        #define ss second
        #define rep(i, a, b) for(int i = a; i < (b); ++i)
        #define per(i, a, b) for(int i = b-1; i>=a ; i--)
        #define trav(a, x) for(auto& a : x)
        #define allin(a , x) for(auto a : x)
        #define td(v) v.begin(),v.end()
        #define sz(v) (int)v.size()
        //#define int long long
        using namespace std;
        typedef vector<int> vi;
        #define y1 abacaba
        #define left sefude
        #define right sefudermano
        typedef long long ll;
        typedef pair<int,int> pii;
        inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
        ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
        ll exp(ll a,ll b,ll m){
            if(b==0LL) return 1LL;
            if(b==1LL) return mod(a,m);
            ll k = mod(exp(a,b/2,m),m);
            if(b&1LL){
                return mod(a*mod(k*k,m),m);
            }
            else return mod(k*k,m);
        }
         
         
        int n,m;
        const int N = 3e4 + 10;
        int b[N],p[N];
         
         
        const int sq = 200;
         
        int mark[N]; 
        int dist[N][sq + 3];
        vi aqui[N];
        int mn[N];
        const int inf = 1e9;
        int rev[N];
        vector<pii> pq[N*sq];
       
        #define pwr(x) (x>sq ? sq + 1 : x)


        int32_t main(){
          fastio;
          cin >> n >> m;
          for(int i=0;i<m;i++){
            cin >> b[i] >> p[i];
            aqui[b[i]].pb(i);
          }

          for(int i=0;i<N;i++){
            mn[i] = inf;
            for(int j=0;j<sq+2;j++)dist[i][j] = inf;
          }
          
          dist[b[0]][pwr(p[0])] =0;
          mn[b[0]] = 0;
          pq[0].pb(pii(b[0],0));
          
          for(int D=0;!pq[D].empty();D++){
          while(!pq[D].empty()){
            pii c = pq[D].back();
            pq[D].pop_back();

            int d = D;
            int cur = c.ff;

            if(mn[cur] > d)mn[cur] = d;
            if(p[c.ss] <= sq){
              aqui[cur].pb(c.ss);
            }

            for(int id : aqui[cur]){
                int x = p[id];
                if(x > sq){
                if(dist[cur][sq+1]==inf)dist[cur][sq+1] = d;
                if(mark[id])continue;
                mark[id] = 1;
                  int t=0;
                  for(int l = cur-x;l>=0;l-=x){
                    t++;
                      pq[d+t].pb(pii(l,id));
                  }
                  t=0;
                  for(int l = cur + x;l<n;l+=x){
                    t++;
                      pq[d+t].pb(pii(l,id));
                    
                  }
                }else{
                  dist[cur][x] = min(dist[cur][x],d);
                  if(cur - x >=0 and dist[cur-x][x] == inf){
                    dist[cur-x][x] = d + 1;

                    pq[d+1].pb(pii(cur - x,id));
                  } 
                  if(cur + x < n and dist[cur + x][x] == inf){
                    dist[cur + x][x] = d + 1;
                    pq[d+1].pb(pii(cur + x,id));
                  }
                }
            } 
            aqui[cur].clear();
            
         
         
          }  

          }
         
          int res = mn[b[1]];
          for(int i=1;i<=sq+1;i++)res = min(res,dist[b[1]][i]);
          if(res == inf)cout<<-1<<endl;
          else cout << res << endl;  
          // Math -> gcd it all
          // Did u check N=1? Did you switch N,M?
        } 

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