Cod sursa(job #1427208)

Utilizator ButnaruButnaru George Butnaru Data 1 mai 2015 18:20:03
Problema Lowest Common Ancestor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct date{ int m; date *next; };
struct data{ int lv,val; };
int n,m,i,j,x,y,nr,pos[100001],v[200001],aux,dif;
date *p,*t[100001];
data rmq[18][200001];
data min(data a,data b){
    if (a.lv>b.lv) return b; else return a;
}
void euler(int nod,int h)
{
    date *a; a=t[nod]; nr++;
    rmq[0][nr].val=nod; rmq[0][nr].lv=h; pos[nod]=nr;
    while (a) {
    euler(a->m,h+1);
    nr++; rmq[0][nr].val=nod; rmq[0][nr].lv=h;
    a=a->next;
    }
}
int main(){
ifstream fin("lca.in");
ofstream fout("lca.out");
fin>>n>>m;
for (i=2;i<=n;i++){
fin>>x; p=new date; p->m=i; p->next=t[x]; t[x]=p;
}
nr=0; euler(1,0);
for (i=1;1<<i<=nr;i++){
   aux=1<<(i-1);
    for (j=1;j+aux<=nr;j++)
     rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+aux]);
}
for (i=2;i<=nr;i++) v[i]=v[i/2]+1;
for (i=1;i<=m;i++){
    fin>>x>>y; x=pos[x]; y=pos[y];
    if (x>y) swap(x,y); dif=v[y-x+1]; aux=1<<dif;
    fout<<min(rmq[dif][x],rmq[dif][y-aux+1]).val<<"\n";
}
return 0;
}