fork download
copy 
  1.  #include<bits/stdc++.h>
  2.  using namespace std;
  3.  #define ll long long
  4.  #define pb push_back
  5.  ll mod =  1e9+7;
  6.  #define f first
  7.  #define ss second
  8.  #define mxx(x) max_element(x.begin(), x.end()) - x.begin()
  9.  #define mnn(x) min_element(x.begin(), x.end()) - x.begin()
  10.  #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  11.  #define all(x) x.begin(), x.end()
  12.  #define sz(x) x.size()
  13.  
  14.  // binary lifting seekh le bro
  15.  
  16.  void test_cases(){
  17.  
  18.      ll n,q;
  19.      ll a , k ;
  20.      cin>>n>>q;
  21.  
  22.      vector<ll>arr(n);
  23.  
  24.      for(ll i = 0; i < n ;i++ ){
  25.          cin>>arr[i];
  26.      }
  27.  
  28.      vector<vector<ll>>up(n , vector<ll>(31, -1));
  29.  
  30.      for(ll i=0;i<n;i++){
  31.          up[i][0] = arr[i]-1;
  32.      }
  33.  
  34.          for(ll j = 1; j < 31; j++){ 
  35.              for(ll i = 0 ; i < n ;i++){
  36.  
  37.              if(up[i][j-1] == -1){
  38.                  up[i][j] = -1;
  39.                  continue;
  40.              }
  41.  
  42.              up[i][j] = up[up[i][j-1]][j-1];
  43.          }
  44.      }
  45.      // 183772 129965406
  46.      while(q--){
  47.  
  48.          cin>>a>>k;
  49.          a--;
  50.  
  51.          ll L = 30;
  52.  
  53.          ll st = a;
  54.          while(L>=0){
  55.              if(1<<L <= k){
  56.                  k-=(1<<L);
  57.                  a = up[a][L];
  58.                  if(a==-1){
  59.                      a = st;
  60.                      break;
  61.                  }
  62.              }
  63.              L--;
  64.          }
  65.          cout<<a+1<<"\n";
  66.      }
  67.  } 
  68.  
  69.  int main(){
  70.  
  71.      fast_io;
  72.      ll t=1;
  73.      // cin>>t;
  74.  
  75.      while(t--){
  76.  
  77.          test_cases();
  78.          cout<<"\n";
  79.      }
  80.  }
Runtime error #stdin #stdout #stderr 0.01s 5512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/pfhKAV
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!