Company Queries II

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#else
#define deb(fmt, args...)
#endif

void print_array(vector<int> in, const string title = "Vector")
{
	cout << title << " [\n";
	for (const auto &el : in) {
		cout << el << " ";
	}
	cout << "\n] END\n";
}

void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	cout << title << " [\n";
	for (unsigned int i = 0; i < in.size(); i++) {
		cout << "row " << i << ": ";
		for (unsigned int j = 0; j < in[i].size(); j++) {
			cout << in[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "] END\n";
}

void dfs(int s, vector<bool> &visited, vector<vector<int> > &adj, int depth,
	 vector<int> &depths)
{
	if (visited[s]) {
		return;
	};
	visited[s] = true;

	depths[s] = depth;
	// traversal.push_back({ s, depth });
	for (auto u : adj[s]) {
		dfs(u, visited, adj, depth + 1, depths);
		// traversal.push_back({ s, depth });
	}
}

int bit_ceil(int n) {
    int res = 1;
    while (res < n) res <<= 1;
    return res >>= 1;
}

int get_ancestor(int in, int d, vector<vector<int> > &ancestors)
{
    int depth = d;
    int next = in;
    int row = 0;
    // while (depth > 0) {
    //     row = bit_ceil(d);
    //     next = ancestors[row][next];
    //     depth -= row;
    // }
    // return next;
	while (depth > 0) {
		if (depth % 2 == 1)
			next = ancestors[row][next];
		row++;
		depth >>= 1;
	}
	return next;
}

int main(int argc, char *argv[])
{
	// Read the input parameters
	int n, q;
	cin >> n >> q;

	// Read values from one line
	// vector<int> boss(n + 1);
	vector<vector<int> > kids(n + 1, vector<int>());
	vector<vector<int> > ancestor(log2(n) + 1, vector<int>(n + 1));
	int tmp;
    // deb("paskaa\n");
	for (int i = 1; i < n; i++) {
		cin >> tmp;
		// boss[i] = tmp - 1;
		ancestor[0][i] = tmp - 1;
		kids[tmp - 1].push_back(i);
	}
	// boss[1] = 0;
	// boss[0] = 0;
	// ancestor[0][1] = 0;
	ancestor[0][0] = 0;

	// print_matrix(kids);


	vector<bool> visited(n, false);
	// vector<int> traversal;
	vector<int> depths(n + 1);
	dfs(0, visited, kids, 0, depths);

	for (unsigned int row = 1; row < ancestor.size(); row++) {
		for (int j = 0; j < n; j++) {
			ancestor[row][j] =
				ancestor[row - 1][ancestor[row - 1][j]];
		}
	}
	// print_matrix(ancestor, "ancestor");
	// print_array(depths, "depths");
    // deb("paskaa3\n");

	int l, r;
	for (int i = 0; i < q; i++) {
		cin >> l >> r;
		l--;
		r--;
		// l = first[l];
		// r = first[r];
		// deb("väli (%d, %d)\n", l, r);
        // increase nodes to same depth
        // deb("r: %d, r: %d, l: %d\n", r, depths[r], depths[l]);
		if (depths[l] > depths[r]) {
			l = get_ancestor(l, depths[l] - depths[r], ancestor);
        } else {
            // deb("r: %d, k: %d", r, dephts[r] - dephts[l]);
            // deb("r: %d, k: %d", r, depths[r] - depths[l]);
			r = get_ancestor(r, depths[r] - depths[l], ancestor);
        }
        // deb("r: %d, l: %d\n", r, l);

        // start traversing top down
		if (l != r) {
			for (int row = ancestor.size() - 1; row >= 0; row--) {
                // if ancestor is different, update positions to get closer
                // deb("l: %d, r: %d, row: %d\n", l, r, row);
				if (ancestor[row][l] != ancestor[row][r]) {
                    // deb("l: %d, r: %d\n", l, r);
					l = ancestor[row][l];
					r = ancestor[row][r];
				}
			}
			l = ancestor[0][l];
		}

		cout << l + 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