# Cod sursa(job #391337)

Utilizator Data 5 februarie 2010 14:47:44 Stramosi 90 cpp done Arhiva de probleme 1.09 kb
``````#include <fstream>
#include <vector>
#include <bitset>
#define maxm 1<<19
#define maxn 400000
#define pb push_back
#define sz size

using namespace std;

ifstream fin ("stramosi.in"); // citire + scriere cu streamuri pt eficienta (cica)
ofstream fout ("stramosi.out");

int N, M, i, p, q , a;
int st [maxm];
vector <int> listv [maxm];
vector <int> listp [maxm], G [maxm];
int sol [maxm], fat [maxm];
bool viz [maxm];

void dfs (int node, int lev) {

int j;
viz [node] = true;
st [lev] = node;
for (j = 0; j < listv [node].sz (); j++)
if (lev > listv [node][j]) sol [listp [node][j]] = st [lev - listv [node][j]];
for (j = 0; j < G [node].sz (); j++)
if (!viz [G [node][j]])
dfs (G [node][j], lev + 1);
}

int main () {

int a;
fin >> N >> M;
for (i = 1; i <= N; i++) {
fin >> a;
fat [i] = a;
G [a].pb (i);
}
for (i = 1; i <= M; i++)
{
fin >> q >> p;
listv [q].pb (p);
listp [q].pb (i);
}
for (i = 1; i <= N; i++)
if (!fat [i])
dfs (i, 1);
for (i = 1; i <= M; i++) fout << sol [i] << "\n";
return 0;
}
``````