Cod sursa(job #2204669)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 16 mai 2018 19:46:18
Problema Stramosi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

#define dbg(x) cerr<<#x": "<<x<<"\n"
#define dbg_p(x) cerr<<#x": "<<x.first<<","<<x.second<<"\n"
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

#define st first
#define nd second

#define DMAX 
#define NMAX 
#define MMAX 

using namespace std;

int n, m, x,q,p;

template<class T>
ostream& operator<<(ostream& out, vector<T> v) {
	out << v.size() << '\n';
	for(auto e : v) out << e << ' ';
	return out;
}

ifstream fin("stramosi.in");
ofstream fout("stramosi.out");

vector<int> v[250005];
int lift[250005][32], par[250005], hist[250005];

void dfs(int nod, int nivel)
{
	hist[nivel]=nod;
		for (int i=0;(1 << i) < nivel;i++)
			lift[nod][i]=hist[nivel-(1<<i)];
	for (auto vec:v[nod])
		dfs(vec,nivel+1);
}

int main() {
	ios_base::sync_with_stdio(false);
	fin>>n>>m;
	for (int i=1;i<=n;i++)
	{
			fin>>x;
			par[i]=x;
			if (x)
				v[x].push_back(i);
	}
	for (int i=1;i<=n;i++)
		if (!par[i])
			dfs(i, 1);
	for (int i=1;i<=m;i++)
	{
		fin>>q>>p;
		for (int j=17;j>=0;j--)
			{
				if ((1<<j)&p)
					q=lift[q][j];
			}
		fout<<q<<'\n';
	}
}