Advertisement
Josif_tepe

Untitled

Aug 13th, 2023
1,216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <stack>
  8. using namespace std;
  9. typedef long long ll;
  10. const int maxn = 2e5 + 10;
  11. const int logn = 18;
  12. int parent[maxn];
  13. int up_node[maxn][logn + 5];
  14. int depth_of_node[maxn];
  15. int main() {
  16.     ios_base::sync_with_stdio(false);
  17.     int n, q;
  18.     cin >> n >> q;
  19.    
  20.     for(int i = 1; i < n; i++) {
  21.         int p;
  22.         cin >> p;
  23.         p--;
  24.         parent[i] = p;
  25.     }
  26.     memset(depth_of_node, 0, sizeof depth_of_node);
  27.     memset(up_node, 0, sizeof up_node);
  28.     parent[0] = 0;
  29.    
  30.     for(int i = 0; i < n; i++) {
  31.         up_node[i][0] = parent[i];
  32.         if(i != 0) {
  33.             depth_of_node[i] = depth_of_node[parent[i]] + 1;
  34.         }
  35.        
  36.         for(int j = 1; j <= logn; j++) {
  37.             up_node[i][j] = up_node[ up_node[i][j - 1] ][j - 1];
  38.         }
  39.     }
  40.    
  41.  
  42.    
  43.     while(q--) {
  44.         int node, k;
  45.         cin >> node >> k;
  46.         node--;
  47.         if(depth_of_node[node] < k) {
  48.             cout << -1 << endl;
  49.             continue;
  50.         }
  51.         for(int i = logn; i >= 0; i--) {
  52.             if(node == -1) {
  53.                 break;
  54.             }
  55.             if(k & (1 << i)) {
  56.                 node = up_node[node][i];
  57.             }
  58.            
  59.         }
  60.         if(node != -1) {
  61.             node++;
  62.         }
  63.         cout << node << endl;
  64.     }
  65.    
  66.     return 0;
  67. }
  68.  
  69. // 200000
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement