Cod sursa(job #159223)

Utilizator city_guy91alex isip city_guy91 Data 14 martie 2008 00:05:06
Problema Stramosi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <stdio.h>
long n,m,a[250001][18],log[250001],p,q,st;
int main()
{
 freopen("stramosi.in","r",stdin);
 freopen("stramosi.out","w",stdout);
 scanf("%ld %ld\n",&n,&m);
 log[1]=0;
 long i,j;
 scanf("%ld",&a[1][0]);
 for (i=2;i<=n;i++)
 {
  log[i]=log[i/2]+1;
  scanf("%ld",&a[i][0]);
 }
 for (i=1;i<=n;i++)
  for (j=1;j<=log[n];j++)
  {
   if (!a[a[i][j-1]][j-1])
    break;
   a[i][j]=a[a[i][j-1]][j-1];
  }
 for (i=0;i<m;i++)
 {
  scanf("%ld %ld\n",&q,&p);
  while (p)
  {
   st=a[q][log[p]];
   p-=(1<<log[p]);
   q=st;                                  
  }
  printf("%ld\n",st);
 }
}