Company Queries II

input/code.cpp: In function 'int calc_LCA(int&, int&, std::vector<std::vector<int> >&, std::vector<std::pair<int, int> >&, int)':
input/code.cpp:40:9: warning: unused variable 'n_employees' [-Wunused-variable]
   40 |     int n_employees = tree.size() - 1;
      |         ^~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:69:9: warning: unused variable 'max_k' [-Wunused-variable]
   69 |     int max_k = pow(2, max_k_power);
      |         ^~~~~

#include <iostream>
#include <vector>
#include <cmath>
#include <bits/stdc++.h>
#include <string>

using namespace std;

int succ(int node, int depth, vector<pair<int, int>> & tree)
{
    if(depth == 1)
    {
        return tree[node].first;
    }
    else
    {
        return succ(succ(node, depth/2, tree), depth/2, tree);
    }
}

void preproc(int max_k_power, vector<vector<int>> & ancestors, vector<pair<int, int>> & tree, vector<int> & depth)
{
    int n_employees = tree.size() - 1;
    for(int i = 1; i <= max_k_power; ++i)
    {
        for(int e = 1; e <= n_employees; ++e)
        {
            ancestors[e][i] = ancestors[ancestors[e][i-1]][i-1];
        }
    }
}

int calc_LCA(int & node1, int & node2, vector<vector<int>> & ancestors, vector<pair<int, int>> & tree, int max_k_power)
{
    if(node1 == node2) return node1;
    if(tree[node1].second < tree[node2].second)
    {
        swap(node1, node2);
    }
    int n_employees = tree.size() - 1;
    int current_diff = tree[node1].second - tree[node2].second;
    for(int i = max_k_power; i >= 0; --i)
    {
        if(pow(2, i) <= current_diff)
        {
            node1 = ancestors[node1][i];
            current_diff = current_diff - pow(2,i);
        }
    }
    if(node1 == node2) return node1;
    for(int i = max_k_power; i >= 0; --i)
    {
        if(ancestors[node1][i] != ancestors[node2][i])
        {
            node1 = ancestors[node1][i];
            node2 = ancestors[node2][i];
        }
    }
    return ancestors[node1][0];
    
}

int main()
{
    long long n_employees;
    long long n_queries;
    cin >> n_employees >> n_queries;
    int max_k_power = floor(log2(n_employees));
    int max_k = pow(2, max_k_power);

    vector<vector<int>> ancestors(n_employees + 1, vector<int>(max_k_power + 1, 0));
    vector<pair<int, int>> tree(n_employees + 1);
    vector<int> depth(n_employees + 1, -1);
    depth[1] = 0;
    tree[1] = {0, 0};
    for(int i = 2; i <= n_employees; ++i)
    {
        int a;
        cin >> a;
        tree[i] = {a, tree[a].second + 1};
        ancestors[i][0] = a;
    }

    preproc(max_k_power, ancestors, tree, depth);

    string bin = "";
    for(int i = 0; i < n_queries; ++i)
    {
        int a, b;
        cin >> a >> b;
        bin.append(to_string(calc_LCA(a, b, ancestors, tree, max_k_power)) + '\n');
    }
    cout << bin;

}

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