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,
	 vector<int> &traversal)
{
	if (visited[s]) {
		return;
	};
	visited[s] = true;
 
	traversal.push_back(s);
	for (auto u : adj[s]) {
		dfs(u, visited, adj, traversal);
		traversal.push_back(s);
	}
}
 
void build_sparse_table(vector<int> &in, vector<vector<int> > &sparse)
{
	int rows = 1;
	rows = log2(in.size()) + 1;
	sparse.clear(); // clear table
    sparse.push_back(vector<int>());
	for (unsigned int i = 0; i < in.size(); i++) {
		sparse[0].push_back(in[i]);
	}
	for (int i = 1; i < rows; i++) {
		sparse.push_back(vector<int>()); // needed rows
		int len = 1 << i;
		int w = len / 2;
		for (unsigned int j = 0; j < in.size() - len + 1; j++) {
			int minimum =
				min(sparse[i - 1][j], sparse[i - 1][j + w]);
			sparse[i].push_back(minimum);
		}
	}
}
 
int query_sparse_table(int a, int b, vector<vector<int> > &sparse)
{
	int L = min(a, b);
	int R = max(a, b);
	int num = 1;
	if (L == R) {
        if (L == 0) return 1;
		return sparse[0][L - 1];
	}
	while (num < R - L)
		num <<= 1;
	if (num != R - L) {
		num >>= 1;
	}
	int row = log2(num);
	return min(sparse[row][L], sparse[row][R - num]);
}
 
int main(int argc, char *argv[])
{
	// Read the input parameters
	int n, q;
	cin >> n >> q;
 
	// Read values from one line
	vector<vector<int> > kids(n + 1, vector<int>());
	int tmp;
	for (int i = 0; i < n - 1; i++) {
		cin >> tmp;
		kids[tmp].push_back(i + 2);
	}
 
	// print_matrix(kids);
 
	// Build traversal array
	vector<bool> visited(n, false);
	vector<int> traversal;
	dfs(1, visited, kids, traversal);
 
	// Find the first occurence of node
	vector<int> first(n + 1, -1);
	for (unsigned int i = 0; i < traversal.size(); i++) {
		if (first[traversal[i]] == -1) {
			first[traversal[i]] = i;
		}
        // deb("i: %d, traversal[i]: %d, first[traversal[i]]: %d\n", i,
        //         traversal[i], first[traversal[i]]);
	}
    // traversal[0] = 1;
	// print_array(traversal, "traversal");
	// print_array(first, "first");
	// Build sparse table
	vector<vector<int> > sparse;
	build_sparse_table(traversal, sparse);
	// print_matrix(sparse);
 
	// Do queries
	int l, r;
	for (int i = 0; i < q; i++) {
		cin >> l >> r;
		l = first[l];
		r = first[r];
		// deb("väli (%d, %d)\n", l, r);
		int res = query_sparse_table(l, r, sparse);
		cout << res << "\n";
	}
 
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER