oj.uz

답안 #243945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243945 2020-07-02T10:27:18 Z NaimSS Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 305 ms 262144 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(mn[cur] > d)mn[cur] = d;
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 166008 KB Output is correct
2 Correct 103 ms 165880 KB Output is correct
3 Correct 105 ms 165880 KB Output is correct
4 Correct 104 ms 165880 KB Output is correct
5 Correct 105 ms 165880 KB Output is correct
6 Correct 103 ms 165880 KB Output is correct
7 Correct 108 ms 165884 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 165880 KB Output is correct
2 Correct 108 ms 165880 KB Output is correct
3 Correct 110 ms 165880 KB Output is correct
4 Correct 124 ms 165880 KB Output is correct
5 Correct 124 ms 165880 KB Output is correct
6 Correct 105 ms 165880 KB Output is correct
7 Correct 105 ms 165880 KB Output is correct
8 Correct 107 ms 165880 KB Output is correct
9 Correct 106 ms 165880 KB Output is correct
10 Correct 103 ms 165880 KB Output is correct
11 Correct 118 ms 165880 KB Output is correct
12 Correct 121 ms 165880 KB Output is correct
13 Correct 103 ms 165880 KB Output is correct
14 Correct 106 ms 166008 KB Output is correct
15 Correct 106 ms 165880 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 165880 KB Output is correct
2 Correct 114 ms 165880 KB Output is correct
3 Correct 105 ms 165880 KB Output is correct
4 Correct 114 ms 165984 KB Output is correct
5 Correct 107 ms 165880 KB Output is correct
6 Correct 114 ms 165880 KB Output is correct
7 Correct 103 ms 165880 KB Output is correct
8 Correct 102 ms 165996 KB Output is correct
9 Correct 106 ms 165880 KB Output is correct
10 Correct 121 ms 165880 KB Output is correct
11 Correct 108 ms 166008 KB Output is correct
12 Correct 115 ms 165880 KB Output is correct
13 Correct 103 ms 165880 KB Output is correct
14 Correct 139 ms 165972 KB Output is correct
15 Correct 115 ms 166008 KB Output is correct
16 Correct 111 ms 165892 KB Output is correct
17 Runtime error 279 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 165880 KB Output is correct
2 Correct 119 ms 165880 KB Output is correct
3 Correct 112 ms 165880 KB Output is correct
4 Correct 107 ms 165880 KB Output is correct
5 Correct 105 ms 165880 KB Output is correct
6 Correct 118 ms 165884 KB Output is correct
7 Correct 104 ms 166008 KB Output is correct
8 Correct 113 ms 165880 KB Output is correct
9 Correct 104 ms 165880 KB Output is correct
10 Correct 115 ms 165880 KB Output is correct
11 Correct 113 ms 165884 KB Output is correct
12 Correct 103 ms 165936 KB Output is correct
13 Correct 120 ms 165880 KB Output is correct
14 Correct 103 ms 165880 KB Output is correct
15 Correct 105 ms 166008 KB Output is correct
16 Correct 106 ms 165900 KB Output is correct
17 Runtime error 285 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 165880 KB Output is correct
2 Correct 118 ms 165868 KB Output is correct
3 Correct 124 ms 165880 KB Output is correct
4 Correct 105 ms 165804 KB Output is correct
5 Correct 104 ms 165880 KB Output is correct
6 Correct 118 ms 165880 KB Output is correct
7 Correct 102 ms 165880 KB Output is correct
8 Correct 114 ms 165884 KB Output is correct
9 Correct 103 ms 165880 KB Output is correct
10 Correct 123 ms 165880 KB Output is correct
11 Correct 107 ms 165880 KB Output is correct
12 Correct 113 ms 165880 KB Output is correct
13 Correct 106 ms 165880 KB Output is correct
14 Correct 105 ms 165880 KB Output is correct
15 Correct 105 ms 165880 KB Output is correct
16 Correct 104 ms 165880 KB Output is correct
17 Runtime error 305 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -