Submission #243944

#	Time	Username	Problem	Language	Result	Execution time	Memory
243944		NaimSS	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	123 ms	166648 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;
        bool vis[N][sq + 2];
         
        int dist[N][sq + 2];
        vi aqui[N];
        int mn[N];
        const int inf = 1e9;
       
        vector<pii> pq[N*sq];
       
        #define pwr(x) (x>=sq ? sq + 1 : x)
        void djkistra(){
          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],p[0]));
          
          for(int D=0;!pq[D].empty();D++){
          while(!pq[D].empty()){
            pii c = pq[D].back();
            pq[D].pop_back();
            if(vis[c.ff][pwr(c.ss)])continue;
            vis[c.ff][pwr(c.ss)]=1;
            int d = dist[c.ff][pwr(c.ss)];
            int id = c.ff;
            int cur = c.ff;
     
            if(c.ss < sq){
              aqui[id].pb(c.ss);
            }
         
            for(int x : aqui[id]){
              
                if(x >= sq){
                  int t=0;
                  for(int l = cur-x;l>=0;l-=x){
                    t++;
                    if(mn[l] > d + t){
                      mn[l] = dist[l][sq+1] = d + t;
                      pq[mn[l]].pb(pii(l,x));
                    }
                  }
                  t=0;
                  for(int l = cur + x;l<n;l+=x){
                    t++;
                    if(mn[l] > d + t){
                      mn[l] = dist[l][sq + 1] = d + t;
                      pq[mn[l]].pb(pii(l,x));
                    }
                  }
                }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;
                    if(mn[cur-x] > d+1)mn[cur-x] = d+1;
                    if(!vis[cur-x][x])pq[d+1].pb(pii(cur - x,x));
                  } 
                  if(cur + x < n and dist[cur + x][x] == inf){
                    dist[cur + x][x] = d + 1;
     
                    if(mn[cur+x] > d+1)mn[cur+x] = d+1;
                    if(!vis[cur+x][x])pq[d+1].pb(pii(cur + x,x));
                  }
                     }
                  } 
            aqui[id].clear();
            
         
         
          }  

          }
         
          int res = mn[b[1]];
          if(res == inf)cout<<-1<<endl;
          else cout << res << endl;
        }
         
        int32_t main(){
          fastio;
          cin >> n >> m;
          for(int i=0;i<m;i++){
            cin >> b[i] >> p[i];
            aqui[b[i]].pb(p[i]);
          }
          djkistra();
          // Math -> gcd it all
          // Did u check N=1? Did you switch N,M?
        } 

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