YEZAELP

o60_oct_c1_deep

Nov 30th, 2021
607
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int maxN = 2e5 + 10;
  5. int L[maxN], R[maxN];
  6. int n, q;
  7. struct Data{int u, b, ch;};
  8. vector <Data> deep[maxN];
  9. int mxdeep = 0;
  10.  
  11. void dfs(int u, int b, int ch, int d){
  12.     deep[d].push_back({u, b, ch});
  13.     mxdeep = max(mxdeep, d);
  14.     if(L[u] == -1 and R[u] == -1) return;
  15.     if(L[u] == -1){
  16.         dfs(R[u], b, ch, d + 1);
  17.     }
  18.     else if(R[u] == -1){
  19.         dfs(L[u], b, ch, d + 1);
  20.     }
  21.     else{
  22.         dfs(L[u], (b << 1) | 0, ch + 1, d + 1);
  23.         dfs(R[u], (b << 1) | 1, ch + 1, d + 1);
  24.     }
  25. }
  26.  
  27. int Dir(int ch, int s, int a, int b){
  28.     int res = 0;
  29.     for(int i=1;i<=ch;i++){
  30.         res = res << 1;
  31.         res = res | ((s & 8) >> 3);
  32.         s = (s * a + b) % 40507;
  33.     }
  34.     return res;
  35. }
  36.  
  37. int Solve(){
  38.     int L, s, a, b;
  39.     scanf("%d %d %d %d", &L, &s, &a, &b);
  40.     L = min(L, mxdeep);
  41.     while(true){
  42.         for(auto i: deep[L]){
  43.             int bit = Dir(i.ch, s, a, b);
  44.             if(bit == i.b)
  45.                 return i.u;
  46.         }
  47.         L --;
  48.     }
  49.     return 0;
  50. }
  51.  
  52. int main(){
  53.  
  54.     cin >> n >> q;
  55.  
  56.     for(int i=0;i<=n-1;i++){
  57.         cin >> L[i] >> R[i];
  58.     }
  59.  
  60.     dfs(0, 0, 0, 0);
  61.  
  62.     while(q --){
  63.         printf("%d\n", Solve());
  64.     }
  65.  
  66.     return 0;
  67. }
  68.  
RAW Paste Data