# Cod sursa(job #928643)

Utilizator Data 26 martie 2013 16:37:20 Stramosi 100 cpp done Arhiva de probleme 1.18 kb
``````#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream f("stramosi.in");
ofstream g("stramosi.out");

const int MAX_N = 250005;

int n, m, tata[MAX_N], nivel[MAX_N], where[MAX_N];
bool frunza[MAX_N];
vector <int> stramos[MAX_N];	// stramos[i] = lista de stramosi a frunzei i

f >> n >> m;
for (int i = 1; i <= n; i++)
frunza[i] = 1;

for (int i = 1; i <= n; i++) {
f >> tata[i];
frunza[tata[i]] = 0;
}
}

void baga(int frunza) {
int nod = frunza;
while (tata[nod] != 0) {
stramos[frunza].push_back(tata[nod]);
where[nod] = frunza;
nivel[tata[nod]] = nivel[nod] + 1;
nod = tata[nod];
}
where[nod] = frunza;
}

void precompute() {
for (int i = 1; i <= n; i++)
if (frunza[i])
baga(i);
}

void solve() {
for (int i = 1; i <= m; i++) {
int Q, P;

f >> Q >> P;
int frnz = where[Q];

if (P == 0)
g << Q << '\n';
else if (P + nivel[Q] - nivel[frnz] - 1 >= stramos[frnz].size())
g << 0 << '\n';
else
g << stramos[frnz][P + nivel[Q] - nivel[frnz] - 1] << '\n';
}
}

int main() {