Company Queries II

input/code.cpp: In function 'void preproc(int, std::vector<std::vector<int> >&, std::vector<std::pair<int, int> >&, std::vector<int>&)':
input/code.cpp:64:13: warning: unused variable 'current_power' [-Wunused-variable]
   64 |         int current_power = pow(2, i);
      |             ^~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:112:9: warning: unused variable 'max_k' [-Wunused-variable]
  112 |     int max_k = pow(2, max_k_power);
      |         ^~~~~

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

using namespace std;

/* int dfsRec(vector<pair<int, int>> & tree, 
vector<int> &visited, int s, vector<int> &res) {
    
    visited[s] = 1;
    int loop = 0;

    // Recursively visit all adjacent 
    // vertices that are not visited yet
    for (int i : tree[s])
    {
        if (visited[i] == 0)
            loop = dfsRec(adj, visited, i, res);
        if (visited[i] == 1)
            return 1;            
    }
    res.push_back(s);
    visited[s] = 2;
    return loop;
}

vector<int> dfs(vector<pair<int, int>> & tree) {
    vector<int> visited(tree.size(), 0);
    vector<int> res;
    int loop = 0;
    // Loop through all vertices 
    for (int i = 1; i < adj.size(); i++) {
        if (visited[i] == 0) {
            loop |= dfsRec(adj, visited, i, res);
        }
    }
    if(loop == 1)
    {
        cout << "IMPOSSIBLE";
        return {};
    }
    return res;
} */

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 = 0; i <= max_k_power; ++i)
    {
        int current_power = pow(2, i);
        for(int e = 1; e <= n_employees; ++e)
        {
            ancestors[e][i] = succ(e, pow(2, i), tree);
            if(depth[ancestors[e][i]] != -1)
            {
                depth[e] = depth[ancestors[e][i]] + pow(2, i);
            }
        }
    }
}

int calc_LCA(int & node1, int & node2, vector<vector<int>> & ancestors, vector<pair<int, int>> & tree, vector<int> & depth)
{
    if(node1 == node2) return node1;
    if(depth[node1] < depth[node2])
    {
        swap(node1, node2);
    }
    int n_employees = tree.size() - 1;
    int current_diff = depth[node1] - depth[node2];
    for(int i = ceil(log2(n_employees)); 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 = ceil(log2(n_employees)); i >= 0; --i)
    {
        if(ancestors[node1][i] != ancestors[node2][i])
        {
            node2 = ancestors[node1][i];
            node2 = ancestors[node1][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);

/*     for(int i = 0; i <= max_k_power; ++i)
    {
        int current_power = pow(2, i);
        for(int e = 1; e <= n_employees; ++e)
        {
            cout << ancestors[e][i] << " ";
        }
        cout << endl;
    }
    cout << endl; */
    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, depth)) + '\n');
    }
    cout << bin;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED