Pagini recente » Cod sursa (job #1926377) | Cod sursa (job #1519081) | Cod sursa (job #2299355) | Cod sursa (job #2217961) | Cod sursa (job #1979888)
#include <fstream>
#include <vector>
#include <stack>
#define maxn 400005
#define maxm 350005
using namespace std;
ifstream f ("stramosi.in");
ofstream g ("stramosi.out");
struct Query{
int pos, father;
};
vector < int > root;
vector < Query > q[maxn];
vector < int > v[maxn];
vector < int > stiva;
stack < int > dfs;
int sol[maxm];
int p[maxn];
int n, m;
int main(){
f >> n >> m;
for(int i = 1; i <= n; ++i){
int x;
f >> x;
if(x) v[x].push_back(i);
else root.push_back(i);
}
for(int i = 1; i <= m; ++i){
int vx, ft;
f >> vx >> ft;
q[vx].push_back((Query){i, ft});
}
for(int i = 0; i < root.size(); ++i){
dfs.push(root[i]);
while(!dfs.empty()){
int u = dfs.top();
dfs.pop();
if(!stiva.empty()){
while(stiva[stiva.size() - 1] != p[u]){
stiva.erase(stiva.begin() - 1 + stiva.size());
}
}
stiva.push_back(u);
for(int i = 0; i < v[u].size(); ++i){
for(int j = 0; j < q[v[u][i]].size(); ++j){
if(q[v[u][i]][j].father < stiva.size() + 1){
sol[q[v[u][i]][j].pos] = stiva[stiva.size() - q[v[u][i]][j].father];
}
}
}
}
}
for(int i = 1; i <= m; ++i) g << sol[i] << '\n';
}