Submission #243781

#	Time	Username	Problem	Language	Result	Execution time	Memory
243781		Leonardo_Paes	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1088 ms	66292 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 = 250;
    int vis[N][sq + 15];
     
    int dist[N][sq + 15];
    vi aqui[N];
    int mn[N];
    const int inf = 1e9;
    struct coisa{
      int dist,cur,p;
      coisa(){}
      coisa(int a,int b,int c){
        dist = a;
        cur = b;
        p = c;
      }
      bool operator<(const coisa& o)const{
        return dist > o.dist;
      }
    };
     
    #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+10;j++)dist[i][j] = inf;
      }
      
      priority_queue<coisa> pq;
      dist[b[0]][pwr(p[0])] =0;
      mn[b[0]] = 0;
      pq.push(coisa(dist[b[0]][pwr(p[0])],b[0],p[0]));
      
      while(!pq.empty()){
        coisa c = pq.top();
        pq.pop();
       
        if(vis[c.cur][pwr(c.p)])continue;
        vis[c.cur][pwr(c.p)]=1;
        int d = dist[c.cur][pwr(c.p)];
        int id = c.cur;
        int cur = c.cur;
 
        if(c.p < sq){
          aqui[id].pb(c.p);
        }
     
        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.push(coisa(mn[l],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.push(coisa(mn[l],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(!vis[cur-x][x])pq.push(coisa(dist[cur-x][x],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(!vis[cur+x][x])pq.push(coisa(dist[cur + x][x],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: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43