oj.uz

Submission #243943

# Submission time Handle Problem Language Result Execution time Memory
243943 2020-07-02T10:21:34 Z NaimSS Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 132 ms 166648 KB 
        #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;
        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;
          }
        };

        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] > 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[d+1].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(!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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 165880 KB Output is correct
2 Correct 102 ms 165880 KB Output is correct
3 Correct 104 ms 165880 KB Output is correct
4 Correct 105 ms 165880 KB Output is correct
5 Correct 102 ms 165872 KB Output is correct
6 Correct 103 ms 165752 KB Output is correct
7 Correct 103 ms 165880 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 165880 KB Output is correct
2 Correct 105 ms 165880 KB Output is correct
3 Correct 104 ms 165812 KB Output is correct
4 Correct 105 ms 165880 KB Output is correct
5 Correct 103 ms 165880 KB Output is correct
6 Correct 110 ms 165880 KB Output is correct
7 Correct 105 ms 165880 KB Output is correct
8 Correct 105 ms 165884 KB Output is correct
9 Correct 106 ms 165880 KB Output is correct
10 Correct 105 ms 166008 KB Output is correct
11 Correct 113 ms 165880 KB Output is correct
12 Correct 106 ms 165880 KB Output is correct
13 Correct 123 ms 165880 KB Output is correct
14 Correct 115 ms 165880 KB Output is correct
15 Correct 119 ms 166008 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 165880 KB Output is correct
2 Correct 104 ms 165816 KB Output is correct
3 Correct 114 ms 165880 KB Output is correct
4 Correct 112 ms 165892 KB Output is correct
5 Correct 106 ms 165884 KB Output is correct
6 Correct 104 ms 165880 KB Output is correct
7 Correct 103 ms 165880 KB Output is correct
8 Correct 117 ms 165880 KB Output is correct
9 Correct 103 ms 165844 KB Output is correct
10 Correct 109 ms 166008 KB Output is correct
11 Correct 105 ms 165880 KB Output is correct
12 Correct 118 ms 165880 KB Output is correct
13 Correct 106 ms 165880 KB Output is correct
14 Correct 121 ms 165880 KB Output is correct
15 Correct 106 ms 165880 KB Output is correct
16 Correct 109 ms 165880 KB Output is correct
17 Correct 113 ms 166136 KB Output is correct
18 Correct 111 ms 165880 KB Output is correct
19 Correct 107 ms 165880 KB Output is correct
20 Correct 107 ms 166392 KB Output is correct
21 Correct 114 ms 166160 KB Output is correct
22 Correct 107 ms 165880 KB Output is correct
23 Correct 109 ms 166432 KB Output is correct
24 Correct 106 ms 166392 KB Output is correct
25 Correct 110 ms 166392 KB Output is correct
26 Correct 104 ms 166492 KB Output is correct
27 Correct 111 ms 166648 KB Output is correct
28 Incorrect 110 ms 165900 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 165988 KB Output is correct
2 Correct 106 ms 165880 KB Output is correct
3 Correct 109 ms 165880 KB Output is correct
4 Correct 109 ms 165880 KB Output is correct
5 Correct 105 ms 165880 KB Output is correct
6 Correct 107 ms 166008 KB Output is correct
7 Correct 106 ms 165880 KB Output is correct
8 Correct 105 ms 165880 KB Output is correct
9 Correct 109 ms 165880 KB Output is correct
10 Correct 111 ms 165832 KB Output is correct
11 Correct 125 ms 165880 KB Output is correct
12 Correct 104 ms 165880 KB Output is correct
13 Correct 102 ms 165880 KB Output is correct
14 Correct 104 ms 165968 KB Output is correct
15 Correct 106 ms 165880 KB Output is correct
16 Correct 120 ms 165880 KB Output is correct
17 Correct 104 ms 166136 KB Output is correct
18 Correct 106 ms 165880 KB Output is correct
19 Correct 109 ms 165880 KB Output is correct
20 Correct 109 ms 166392 KB Output is correct
21 Correct 105 ms 165880 KB Output is correct
22 Correct 107 ms 165880 KB Output is correct
23 Correct 119 ms 166264 KB Output is correct
24 Correct 110 ms 166392 KB Output is correct
25 Correct 109 ms 166392 KB Output is correct
26 Correct 108 ms 166520 KB Output is correct
27 Correct 107 ms 166520 KB Output is correct
28 Incorrect 112 ms 166068 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 165856 KB Output is correct
2 Correct 103 ms 165880 KB Output is correct
3 Correct 105 ms 165880 KB Output is correct
4 Correct 105 ms 165880 KB Output is correct
5 Correct 105 ms 165856 KB Output is correct
6 Correct 104 ms 165880 KB Output is correct
7 Correct 110 ms 165880 KB Output is correct
8 Correct 108 ms 166008 KB Output is correct
9 Correct 111 ms 165880 KB Output is correct
10 Correct 112 ms 165880 KB Output is correct
11 Correct 108 ms 166012 KB Output is correct
12 Correct 115 ms 165880 KB Output is correct
13 Correct 115 ms 165880 KB Output is correct
14 Correct 114 ms 165880 KB Output is correct
15 Correct 108 ms 165880 KB Output is correct
16 Correct 106 ms 165880 KB Output is correct
17 Correct 116 ms 166136 KB Output is correct
18 Correct 107 ms 165880 KB Output is correct
19 Correct 106 ms 165924 KB Output is correct
20 Correct 132 ms 166392 KB Output is correct
21 Correct 127 ms 166008 KB Output is correct
22 Correct 121 ms 165880 KB Output is correct
23 Correct 128 ms 166264 KB Output is correct
24 Correct 130 ms 166396 KB Output is correct
25 Correct 109 ms 166392 KB Output is correct
26 Correct 105 ms 166648 KB Output is correct
27 Correct 110 ms 166520 KB Output is correct
28 Incorrect 108 ms 165880 KB Output isn't correct
29 Halted 0 ms 0 KB -