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_pair_ar(vector<pair<int, int>> in, const string title = "Vector")
// {
// 	cout << title << " [\n";
// 	for (unsigned int i = 0; i < in.size(); i++) {
//         pair<int, int> el = in[i];
// 		cout << "row " << i << ": " << "{" << el.first << ", " << el.second << "} \n";
// 	}
// 	cout << "\n] END\n";
// }
 
// 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<pair<int, int> > &traversal, int depth)
{
	if (visited[s]) {
		return;
	};
	visited[s] = true;
 
	traversal.push_back({ s, depth });
	for (auto u : adj[s]) {
		dfs(u, visited, adj, traversal, depth + 1);
		traversal.push_back({ s, depth });
	}
}
 
void build_sparse_table(vector<pair<int, int> > &in,
			vector<vector<pair<int, int> > > &sparse)
{
	int rows = 1;
	rows = log2(in.size()) + 1;
	sparse.clear(); // clear table
	sparse.push_back(vector<pair<int, 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<pair<int, int> >()); // needed rows
		int len = 1 << i;
		int w = len / 2;
		for (unsigned int j = 0; j < in.size() - len + 1; j++) {
			pair<int, int> minimum =
				sparse[i - 1][j].second <
						sparse[i - 1][j + w].second ?
					sparse[i - 1][j] :
					sparse[i - 1][j + w];
			// 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<pair<int, int> > > &sparse)
{
	int L = min(a, b);
	int R = max(a, b);
	// deb("L: %d, R: %d\n", L, R);
	int num = 1;
	if (L == R) {
		if (L == 0)
            return 1;
		return sparse[0][L - 1].first;
	}
	while (num < R - L)
		num <<= 1;
	if (num != R - L) {
		num >>= 1;
	}
	int row = log2(num);
	int el = sparse[row][L].second < sparse[row][R - num].second ?
			 sparse[row][L].first :
			 sparse[row][R - num].first;
	return el;
	// return min(sparse[row][L].first, sparse[row][R - num].first);
}
 
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<pair<int, int> > traversal;
	dfs(1, visited, kids, traversal, 1);
 
	// 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].first] == -1) {
			first[traversal[i].first] = i;
		}
		// deb("i: %d, traversal[i]: %d, first[traversal[i]]: %d\n", i,
		//         traversal[i], first[traversal[i]]);
	}
	// first[0] = 0;
	// print_pair_ar(traversal, "traversal");
	// print_array(first, "first");
	// Build sparse table
	vector<vector<pair<int, int> > > sparse;
	build_sparse_table(traversal, sparse);
    // for (unsigned int i = 0; i < sparse.size(); i++) {
    //     print_pair_ar(sparse[i]);
    // }
	// print_matrix(sparse);
 
	// Do queries
	int l, r;
	for (int i = 0; i < q; i++) {
		cin >> l >> r;
		// deb("l: %d, r: %d\n", l, r);
		l = max(first[l] - 1, 0);
		// 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: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

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