Pagini recente » Cod sursa (job #924620) | Cod sursa (job #1039003) | Cod sursa (job #589346) | 4_me | Cod sursa (job #1674309)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("stramosi.in");
ofstream out("stramosi.out");
void adauga(int);
void read(void);
void dfs(int);
void query(void);
const int N_max = 250002;
const int M_max = 300002;
const int Log = 20;
int lst[N_max];
int urm[N_max];
int vf[N_max];
int nr;
int tata[N_max];
int level[N_max];
bool viz[N_max];
int A[N_max][Log]; /* A[i][j] == AL 2 ^ j STRAMOS AL LUI i */
int N, Q;
void adauga(int x, int y)
{
// ADAUGA IN LISTA LUI x PE y
nr++;
vf[nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
void read()
{
int i, j;
in >> N >> Q;
for(i = 1; i <= N; i++)
{
in >> tata[i];
adauga(tata[i], i);
}
for(i = 1; i <= N; i++)
if(!tata[i]) dfs(i);
/* CONSTRUIESC MATRICEA A */
for(i = 1; i <= N; i++) A[i][0] = tata[i]; /* PRIMUL STRAMOS AL NODULUI i ESTE CHIAR TATAL ACESTUIA */
for(i = 1; i <= N; i++)
for(j = 1; (1 << j) <= N; j++)
/* RECURENTA */
if(A[i][j - 1]) A[i][j] = A[ A[i][j - 1] ][j - 1];
}
void dfs(int x)
{
int p, y;
viz[x] = true;
// PARCURG VECINII y AI LUI x
p = lst[x];
while(p != 0)
{
y = vf[p];
if(!viz[y])
{
level[y] = 1 + level[x];
dfs(y);
}
p = urm[p];
}
}
void query()
{
int node, P, j;
for(int i = 1; i <= Q; i++)
{
in >> node >> P;
int L = level[node] - P;
int lg;
for(lg = 0; (1 << lg) <= level[node]; lg++);
lg--;
for(j = lg; j >= 0; j--)
if(A[node][j] && level[A[node][j]] >= L) node = A[node][j];
/* ACUM NODUL node SE AFLA PE NIVELUL L. AFISEZ SOLUTIA */
if(L >= 0) out << node << '\n';
else
out << 0 << '\n';
}
}
int main()
{
read();
query();
return 0;
}