Pagini recente » Borderou de evaluare (job #2044232) | Istoria paginii problema/medie | Atasamentele paginii Profil 1oliviac8123tg6 | Centru2 | Cod sursa (job #2447038)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
#define UNASSIGNED_VAL 300000
unsigned int get_ancestor(unsigned int **anc_arr, unsigned int current_node,
unsigned int ancestor_num) {
if(*(anc_arr[current_node] + ancestor_num) != UNASSIGNED_VAL)
return *(anc_arr[current_node] + ancestor_num);
unsigned int i = 1;
while( *(anc_arr[current_node]+i) != UNASSIGNED_VAL ) i++;
*(anc_arr[current_node] + ancestor_num) = get_ancestor(anc_arr, *(anc_arr[current_node]+i-1), ancestor_num - i);
unsigned int a_node = *(anc_arr[current_node]+i-1), a_node_index = i - 1;
for(; i < ancestor_num ; i++)
*(anc_arr[current_node]+i) = *(anc_arr[a_node]+i- a_node_index);
return *(anc_arr[current_node] + ancestor_num);
}
int main() {
ifstream myinpf ("stramosi.in");
unsigned int N, M, anc, a, next_node, c, d;
myinpf >> N >> M;
unsigned int * anc_arr[N+1];
unsigned int depth_arr[N+1];
depth_arr[0] = 0;
anc_arr[0] = NULL;
unsigned int i, j;
for(i = 1 ; i < N + 1; i++) {
myinpf >> anc;
depth_arr[i] = depth_arr[anc] + 1;
anc_arr[i] = new unsigned int [depth_arr[i]];
*(anc_arr[i]) = anc;
for(j = 1 ; j < depth_arr[i] ; j++)
*(anc_arr[i] + j) = UNASSIGNED_VAL;
}
ofstream myoutf ("stramosi.out");
stack<unsigned int> s;
for(i = 0 ; i < M ; i++) {
myinpf >> a >> anc;
if(anc >= depth_arr[a])
myoutf << 0 << "\n";
else
myoutf << get_ancestor(anc_arr, a, anc - 1) << "\n";
}
myoutf.close();
myinpf.close();
for(i = 1 ; i < N + 1 ; i++)
delete[] anc_arr[i];
return 0;
}