Company Queries II

input/code.cpp: In function 'std::vector<std::vector<int> > buildSparseTable(std::vector<int>&)':
input/code.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i=0;i<arr.size();i++){
      |                  ~^~~~~~~~~~~
input/code.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int l=2; l<=arr.size()-1; l*=2){
      |                   ~^~~~~~~~~~~~~~
input/code.cpp:34:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int start=1; start+l-1<=arr.size()-1;start++){
      |                           ~~~~~~~~~^~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void dfs(vector<vector<int>> & g, vector<int> & depth, vector<int>& tour, vector<int>& last, int node, int d){
    depth.push_back(d);
    tour.push_back(node);

    for (int adj: g[node]){
        dfs(g, depth, tour, last, adj, d+1);
        tour.push_back(node);
        depth.push_back(d);
    }

    last[node]=tour.size()-1;
}



vector<vector<int>> buildSparseTable(vector<int> & arr){
    vector<vector<int>> sparse;

    vector<int> firstLevel(arr.size());
    for (int i=0;i<arr.size();i++){
        firstLevel[i]=i;
    }
    sparse.push_back(firstLevel);
    int level=1;
    for (int l=2; l<=arr.size()-1; l*=2){
        int half=l/2;
        vector<int> currLevel(arr.size());
        for (int start=1; start+l-1<=arr.size()-1;start++){
            int lBest=sparse[level-1][start];
            int rBest=sparse[level-1][start+half];
            if (arr[lBest]<=arr[rBest]){
                currLevel[start]=lBest;
            } else {
                currLevel[start]=rBest;
            }
        }
        sparse.push_back(currLevel);
        level++;
    }
    return sparse;
}

int queryMinIndex(vector<int> & arr, vector<vector<int>> & sparse, int l, int r){
    int level=__lg(r-l+1);
    int length=pow(2, level);
    int lBest=sparse[level][l];
    int rBest=sparse[level][r-length+1];
    if (arr[lBest]<=arr[rBest]){
        return lBest;
    } else {
        return rBest;
    }
}

int main(){
    int n, q;
    cin >> n >> q;
    vector<int> arr(n+1);
    vector<vector<int>> g(n+1,vector<int>(0));
    for (int i=2;i<=n;i++){
        int a;
        cin >> a;
        g[a].push_back(i);
    }

    vector<int> depth(1);
    vector<int> tour(1);
    vector<int> last(n+1);

    dfs(g, depth, tour, last, 1, 0);

    auto sparse = buildSparseTable(depth);

    for (int i=0;i<q;i++){
        int l, r;
        cin >> l >> r;
        cout << tour[queryMinIndex(depth, sparse, min(last[l],last[r]), max(last[l],last[r]))] << '\n';
    }
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED