Company Queries II

input/code.cpp: In function 'int main()':
input/code.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'ull' {aka 'long long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0; i<q; i++){
      |                  ~^~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
 
int n;
int logn;
int d[2*200000+1];
int f[2*200000+1];
int e[2*(2*200000+1)];
int didx = 0;
#define logn_max 20
int rmq[(2*200000+1)*logn_max];
map<int,vector<int>> adj;
 
void dfs(int a, int di){
    d[a] = di;
    f[a] = didx;
    e[didx++] = a;
    if(adj.count(a)){
        for(auto b : adj[a]){
            dfs(b, di+1);
            e[didx++] = a;
        }
    }
}
 
void makermq(){
    rmq[1] = 0;
    for(int i=2; i<=didx; i++)
        rmq[i]=rmq[i/2] + 1;
    
    for(int i=0; i<didx; i++){
        rmq[i*logn_max + 0] = e[i];
    }
    for(int j=1; (1<<j)<=didx; j++){
        for(int i=0; i+(1<<j)<=didx; i++){
            int l = rmq[i*logn_max + j - 1];
            int r = rmq[(i + (1 << (j - 1)))*logn_max + (j-1)];
 
            int ln = e[l];
            int rn = e[r];
 
            rmq[i*logn_max + j] = d[ln] < d[rn] ? l : r;
        }
    }
}
 
int main(){
    ull q;
    cin >> n >> q;
 
    for(int i=0; i<n-1; i++){
        int b;
        cin >> b;
        adj[b].push_back(i+2);
    }
 
    dfs(1, 1);
    makermq();
 
    for(int i=0; i<q; i++){
        ll a, b;
        cin >> a >> b;
        
        a = f[a];
        b = f[b];
        if(a > b) swap(a, b);
 
        ll l = b-a+1;
        ll k = floor(log2(l));
 
        int li = rmq[a *logn_max + k];
        int ri = rmq[(b - (1 << k) + 1) *logn_max + k];
 
        int ln = e[li];
        int rn = e[ri];
        cout << e[(d[ln] < d[rn]) ? li : ri] << endl;
    }
}
 

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER