Pagini recente » Borderou de evaluare (job #2637563) | Cod sursa (job #2443469)
#include <fstream>
#include <vector>
using namespace std;
#define N 250003
#define M 300003
ifstream fin("stramosi.in");
ofstream fout("stramosi.out");
struct nod{
int index;
vector<int> sons;
}v[N];
struct wee{
int poz, p;
};
vector<wee> q[N];
int sol[M], n, m;
bool b[N];
void DFSsolve(int x)
{
int Stack[N], vf=0;
Stack[++vf]=x;
for(int i=0;i<q[Stack[vf]].size();++i)
{
if(q[Stack[vf]][i].p>=vf) sol[q[Stack[vf]][i].poz]=0;
else sol[q[Stack[vf]][i].poz]=Stack[vf-q[Stack[vf]][i].p];
}
while(vf)
{
if(v[Stack[vf]].index<v[Stack[vf]].sons.size())
{
Stack[vf+1]=v[Stack[vf]].sons[v[Stack[vf]].index];
v[Stack[vf]].index++;
vf++;
for(int i=0;i<q[Stack[vf]].size();++i)
{
if(q[Stack[vf]][i].p>=vf) sol[q[Stack[vf]][i].poz]=0;
else sol[q[Stack[vf]][i].poz]=Stack[vf-q[Stack[vf]][i].p];
}
}
else vf--;
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=n;++i)
{
int x;
fin>>x;
v[x].sons.push_back(i);
v[i].index=0;
if(x==0) b[i]=1;
}
for(int i=1;i<=m;++i)
{
int x, y;
fin>>x>>y;
wee z;
z.poz=i, z.p=y;
q[x].push_back(z);
}
for(int i=1;i<=n;++i)
if(b[i]) DFSsolve(i);
for(int i=1;i<=m;++i) fout<<sol[i]<<"\n";
fout<<"\n";
return 0;
}