oj.uz

Submission #243944

# Submission time Handle Problem Language Result Execution time Memory
243944 2020-07-02T10:23:14 Z NaimSS Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 123 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;
       
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 165880 KB Output is correct
2 Correct 108 ms 165880 KB Output is correct
3 Correct 118 ms 165880 KB Output is correct
4 Correct 107 ms 165880 KB Output is correct
5 Correct 118 ms 165880 KB Output is correct
6 Correct 103 ms 165880 KB Output is correct
7 Correct 112 ms 165880 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 165880 KB Output is correct
2 Correct 104 ms 165880 KB Output is correct
3 Correct 105 ms 165776 KB Output is correct
4 Correct 105 ms 165880 KB Output is correct
5 Correct 107 ms 165880 KB Output is correct
6 Correct 103 ms 165880 KB Output is correct
7 Correct 108 ms 165884 KB Output is correct
8 Correct 114 ms 165880 KB Output is correct
9 Correct 108 ms 166008 KB Output is correct
10 Correct 104 ms 165880 KB Output is correct
11 Correct 106 ms 166008 KB Output is correct
12 Correct 109 ms 165880 KB Output is correct
13 Correct 104 ms 165880 KB Output is correct
14 Correct 108 ms 166136 KB Output is correct
15 Correct 109 ms 165880 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 165880 KB Output is correct
2 Correct 103 ms 165880 KB Output is correct
3 Correct 106 ms 165880 KB Output is correct
4 Correct 106 ms 165880 KB Output is correct
5 Correct 107 ms 165796 KB Output is correct
6 Correct 103 ms 165752 KB Output is correct
7 Correct 114 ms 165880 KB Output is correct
8 Correct 104 ms 165880 KB Output is correct
9 Correct 107 ms 165880 KB Output is correct
10 Correct 103 ms 165880 KB Output is correct
11 Correct 116 ms 165984 KB Output is correct
12 Correct 107 ms 165852 KB Output is correct
13 Correct 117 ms 165880 KB Output is correct
14 Correct 107 ms 166012 KB Output is correct
15 Correct 116 ms 165884 KB Output is correct
16 Correct 106 ms 165880 KB Output is correct
17 Correct 107 ms 166136 KB Output is correct
18 Correct 109 ms 165880 KB Output is correct
19 Correct 104 ms 165864 KB Output is correct
20 Correct 108 ms 166392 KB Output is correct
21 Correct 107 ms 165864 KB Output is correct
22 Correct 107 ms 165880 KB Output is correct
23 Correct 106 ms 166284 KB Output is correct
24 Correct 116 ms 166392 KB Output is correct
25 Correct 107 ms 166392 KB Output is correct
26 Correct 105 ms 166520 KB Output is correct
27 Correct 109 ms 166648 KB Output is correct
28 Incorrect 103 ms 165880 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 165880 KB Output is correct
2 Correct 106 ms 165880 KB Output is correct
3 Correct 106 ms 165880 KB Output is correct
4 Correct 108 ms 165880 KB Output is correct
5 Correct 104 ms 165880 KB Output is correct
6 Correct 106 ms 165880 KB Output is correct
7 Correct 104 ms 165880 KB Output is correct
8 Correct 105 ms 166008 KB Output is correct
9 Correct 119 ms 165880 KB Output is correct
10 Correct 105 ms 165880 KB Output is correct
11 Correct 108 ms 165880 KB Output is correct
12 Correct 120 ms 165880 KB Output is correct
13 Correct 106 ms 165880 KB Output is correct
14 Correct 117 ms 166008 KB Output is correct
15 Correct 104 ms 165880 KB Output is correct
16 Correct 106 ms 165880 KB Output is correct
17 Correct 106 ms 166136 KB Output is correct
18 Correct 117 ms 165880 KB Output is correct
19 Correct 108 ms 165880 KB Output is correct
20 Correct 112 ms 166444 KB Output is correct
21 Correct 107 ms 165880 KB Output is correct
22 Correct 104 ms 165880 KB Output is correct
23 Correct 112 ms 166392 KB Output is correct
24 Correct 123 ms 166392 KB Output is correct
25 Correct 106 ms 166368 KB Output is correct
26 Correct 104 ms 166520 KB Output is correct
27 Correct 113 ms 166628 KB Output is correct
28 Incorrect 107 ms 165880 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 165880 KB Output is correct
2 Correct 104 ms 165880 KB Output is correct
3 Correct 104 ms 165880 KB Output is correct
4 Correct 104 ms 165880 KB Output is correct
5 Correct 102 ms 165880 KB Output is correct
6 Correct 104 ms 165820 KB Output is correct
7 Correct 104 ms 165880 KB Output is correct
8 Correct 106 ms 165880 KB Output is correct
9 Correct 118 ms 165880 KB Output is correct
10 Correct 103 ms 165880 KB Output is correct
11 Correct 104 ms 166008 KB Output is correct
12 Correct 103 ms 166008 KB Output is correct
13 Correct 107 ms 165880 KB Output is correct
14 Correct 104 ms 166008 KB Output is correct
15 Correct 116 ms 166008 KB Output is correct
16 Correct 117 ms 165880 KB Output is correct
17 Correct 105 ms 166136 KB Output is correct
18 Correct 106 ms 165880 KB Output is correct
19 Correct 104 ms 165880 KB Output is correct
20 Correct 104 ms 166392 KB Output is correct
21 Correct 104 ms 165880 KB Output is correct
22 Correct 105 ms 165880 KB Output is correct
23 Correct 107 ms 166264 KB Output is correct
24 Correct 109 ms 166392 KB Output is correct
25 Correct 117 ms 166392 KB Output is correct
26 Correct 105 ms 166484 KB Output is correct
27 Correct 115 ms 166520 KB Output is correct
28 Incorrect 105 ms 165892 KB Output isn't correct
29 Halted 0 ms 0 KB -