Company Queries II

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll n;
ll logn;
ll d[2*200000+1];
ll f[2*200000+1];
ll e[2*(2*200000+1)];
ll didx = 0;
#define logn_max 20
ll rmq[(2*200000+1)*logn_max];
map<ll,vector<ll>> adj;

void dfs(ll a, ll 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(){
    for(ll i=0; i<didx; i++){
        rmq[i*logn_max + 0] = e[i];
    }
    for(ll j=1; (1<<j)<=didx; j++){
        for(ll i=0; i+(1<<j)<=didx; i++){
            ll l = rmq[i*logn_max + j - 1];
            ll r = rmq[(i + (1 << (j - 1)))*logn_max + (j-1)];

            ll ln = e[l];
            ll rn = e[r];

            rmq[i*logn_max + j] = d[ln] < d[rn] ? l : r;
        }
    }
}

int main(){
    ull q;
    cin >> n >> q;

    for(ll i=0; i<n-1; i++){
        ll b;
        cin >> b;
        adj[b].push_back(i+2);
    }

    // for(auto& [b,vec] : adj){
    //     sort( vec.begin(), vec.end() );
    //     vec.erase( unique( vec.begin(), vec.end() ), vec.end() );
    // }

    dfs(1, 0);
    makermq();

    for(ll i=0; i<q; i++){
        ll qa, qb;
        cin >> qa >> qb;
        if(qa == qb){
            cout << qa << endl;
            continue;
        }

        ll a = f[qa];
        ll b = f[qb];
        if(a > b) swap(a, b);

        ll l = b-a+1;
        ll k = floor(log2(l));

        ll li = rmq[a *logn_max + k];
        ll ri = rmq[(b - (1 << k) + 1) *logn_max + k];

        ll ln = e[li];
        ll rn = e[ri];
        // cout << (e[(d[ln] < d[rn]) ? li : ri] - 1) << endl;
        cout << (e[(d[ln] < d[rn]) ? li : ri]) << endl;
    }
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

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: ACCEPTED

Test 12

Verdict: WRONG ANSWER