Submission #243948

#	Time	Username	Problem	Language	Result	Execution time	Memory
243948		NaimSS	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	57 ms	53240 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 = 30100;
            int b[N],p[N];
             
             
            const int sq = 200;
            int vis[N][sq + 3];
             
            int dist[N][sq + 3];
            vi aqui[N];
            int mn[N];
            const int inf = 1e9;
             
            #define pwr(x) (x>=sq ? sq + 1 : x)
            deque<vector<pii>> pq;
     
            void djkistra(){
              for(int i=0;i<N;i++){
                mn[i] = inf;
                for(int j=0;j<sq+2;j++)dist[i][j] = inf;
              }
              pq.pb(vector<pii>());
              dist[b[0]][pwr(p[0])] =0;
              mn[b[0]] = 0;
              pq[0].pb(pii(b[0],p[0]));
              int cur_d=0,max_d=0;
              while(true){
                while(cur_d <= max_d and pq[0].empty()){
                  cur_d++;
                  pq.pop_front();
                }
                if(cur_d > max_d)break;
                pii c = pq[0].back();
                pq[0].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;
                          if(mn[l] > max_d){
                            pq.pb(vector<pii>());
                            max_d++;
                          }
                          pq[d+t - cur_d].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;
                          if(mn[l] > max_d){
                            pq.pb(vector<pii>());
                            max_d++;
                          }
                          pq[d+t - cur_d].pb(pii(l,x));
                        }
                      }
                    }else{
                      dist[cur][x] = min(dist[cur][x],d);
                      if(cur - x >=0 and dist[cur-x][x] > d + 1){
                        dist[cur-x][x] = d + 1;
                        if(mn[cur-x] > d+1)mn[cur-x] = d+1;
                        if(d+1 > max_d){
                            pq.pb(vector<pii>());
                            max_d++;
                          }
                        if(!vis[cur-x][x])pq[d+1-cur_d].pb(pii(cur - x,x));
                      } 
                      if(cur + x < n and dist[cur + x][x] > d + 1){
                        dist[cur + x][x] = d + 1;
                          
                        if(mn[cur+x] > d+1)mn[cur+x] = d+1;
                        if(d+1 > max_d){
                            pq.pb(vector<pii>());
                            max_d++;
                          }
                        if(!vis[cur+x][x])pq[d+1-cur_d].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