Cod sursa(job #1695412)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 27 aprilie 2016 01:23:04
Problema Stramosi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <vector>
using namespace std;

#define MAXNUM 250005

vector <int> tree[MAXNUM];
int ancestors[19][MAXNUM];
int n, m;

int lg2(int x)
{
	int i;

	for (i = 0; (1 << i) <= x; i++);

	return i - 1;
}

void DFS(int node, int depth, vector<int>* stack)
{
	stack->push_back(node);

	for (int i = 0; (1 << i) <= depth; i++)
	{
		ancestors[i][node] = (*stack)[depth - 1 - i];
	}

	for (int i = 0; i < (int)tree[node].size(); i++)
	{
		DFS(tree[node][i], depth + 1, stack);
	}

	stack->pop_back();
}

int getAncestor(int node, int p)
{
	if (node == 0)
		return 0;

	int l = lg2(p);

	if ((1 << l) == p)
		return ancestors[l][node];
	else
		return getAncestor(ancestors[l][node], p - (1 << l));
}

int main()
{
	freopen("stramosi.in", "r", stdin);
	freopen("stramosi.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		int ancestor;
		scanf("%d", &ancestor);
		
		tree[ancestor].push_back(i);
	}

	vector<int>* stack = new vector<int>();
	DFS(0, 0, stack);

	for (int i = 1; i <= m; i++)
	{
		int p, node;
		scanf("%d %d", &node, &p);

		printf("%d\n", getAncestor(node, p));
	}
}