Company Queries II

input/code.cpp: In function 'int main()':
input/code.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < visited_nbr.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
input/code.cpp:47:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int b = 0; b + length <= visited_nbr.size(); ++b) {
      |                         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;

int n, q;
vector<vector<int>> tree;
vector<int> visited_nbr, visited_depth, first;
vector<vector<pair<int,int>>> min_queries;

void dfs(int x, int d) {
    first[x] = visited_nbr.size();
    visited_nbr.push_back(x);
    visited_depth.push_back(d);
    for (int node : tree[x]) {
        dfs(node, d+1);
        visited_nbr.push_back(x);
        visited_depth.push_back(d);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    vector<int> boss(n-1);
    for (int i = 0; i < n-1; i++) cin >> boss[i];

    tree.assign(n, {});
    for (int i = 1; i < n; i++)
        tree[boss[i-1]-1].push_back(i);

    visited_nbr.clear();
    visited_depth.clear();
    first.assign(n, 0);
    dfs(0, 0);

    int m = floor(log2(visited_nbr.size()))+1;

    min_queries.assign(m, vector<pair<int,int>>(visited_nbr.size()));

    for (int i = 0; i < visited_nbr.size(); ++i)
        min_queries[0][i] = {visited_depth[i], i};

    for (int a = 1; a < m; ++a) {
        int length = 1 << a;
        int half = length >> 1;
        for (int b = 0; b + length <= visited_nbr.size(); ++b) {
            auto left = min_queries[a - 1][b];
            auto right = min_queries[a - 1][b + half];
            min_queries[a][b] = (left.first <= right.first) ? left : right;
        }
    }

    auto compute_minimum = [&](int a, int b) -> int {
        int length = b-a+1;
        int k = 31-__builtin_clz(length);
        auto left = min_queries[k][a];
        auto right = min_queries[k][b-(1 << k)+1];
        auto res = (left.first <= right.first) ? left : right;
        return visited_nbr[res.second];
    };

    while (q--) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        int idxA = first[a];
        int idxB = first[b];
        if (idxA > idxB) swap(idxA, idxB);
        cout << compute_minimum(idxA, idxB) + 1 << "\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