Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int maxN = 2e5 + 10;
- int L[maxN], R[maxN];
- int n, q;
- struct Data{int u, b, ch;};
- vector <Data> deep[maxN];
- int mxdeep = 0;
- void dfs(int u, int b, int ch, int d){
- deep[d].push_back({u, b, ch});
- mxdeep = max(mxdeep, d);
- if(L[u] == -1 and R[u] == -1) return;
- if(L[u] == -1){
- dfs(R[u], b, ch, d + 1);
- }
- else if(R[u] == -1){
- dfs(L[u], b, ch, d + 1);
- }
- else{
- dfs(L[u], (b << 1) | 0, ch + 1, d + 1);
- dfs(R[u], (b << 1) | 1, ch + 1, d + 1);
- }
- }
- int Dir(int ch, int s, int a, int b){
- int res = 0;
- for(int i=1;i<=ch;i++){
- res = res << 1;
- res = res | ((s & 8) >> 3);
- s = (s * a + b) % 40507;
- }
- return res;
- }
- int Solve(){
- int L, s, a, b;
- scanf("%d %d %d %d", &L, &s, &a, &b);
- L = min(L, mxdeep);
- while(true){
- for(auto i: deep[L]){
- int bit = Dir(i.ch, s, a, b);
- if(bit == i.b)
- return i.u;
- }
- L --;
- }
- return 0;
- }
- int main(){
- cin >> n >> q;
- for(int i=0;i<=n-1;i++){
- cin >> L[i] >> R[i];
- }
- dfs(0, 0, 0, 0);
- while(q --){
- printf("%d\n", Solve());
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement