Cod sursa(job #1428211)

Utilizator o_micBianca Costin o_mic Data 3 mai 2015 21:59:45
Problema Stramosi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#define LL long long
#define DN 250005
using namespace std;

int anc[DN][55];

int biggest_power(int x, int &i){
  int p = 0;
  i = 1;
  while(i <= x){
    i *= 2;
    ++p;
  }
  i /= 2;
  return p-1;
}

int find_anc(int x, int p){
  if(p == 0)
    return x;
  int res;
  int power = biggest_power(p, res);
  return find_anc(anc[x][power], p - res);
}

int main() {
  int n, m, x, p;
  ifstream fin("stramosi.in");
  ofstream fout("stramosi.out");
  fin >> n >> m;
  for(int i = 1; i <= n; ++i){
    fin >> anc[i][0];
  }
  for(int j = 1; j < 20; ++j)
    for(int i = 1; i <= n; ++i){
      anc[i][j] = anc[anc[i][j-1]][j-1];
    }

  for(int i = 0; i < m; ++i){
    fin >> x >> p;
    fout << find_anc(x, p) << '\n';
  }
  return 0;
}