Cod sursa(job #928027)

Utilizator valentina506Moraru Valentina valentina506 Data 26 martie 2013 10:49:16
Problema Lowest Common Ancestor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
#include<vector>
using namespace std;
ofstream g("lca.out");
int n,m,i,j,t[100001],ap[100001],b[400001],niv[400001],nr,lg[100001];
vector<int>a[100001];
int rmq[20][400001],x,y;
void df(int x,int l)
{
    b[++nr]=x;
    niv[nr]=l;
    ap[x]=nr;
    for(int i=0;i<a[x].size();++i)
    {
        df(a[x][i],l+1);
        b[++nr]=x;
        niv[nr]=l;
    }
}
int lca(int x, int y)
{
    int sol,a,b,dif,l;
    a=ap[x];
    b=ap[y];
    if(a>b)
    swap(a,b);
    dif=b-a+1;
    l=lg[dif];
    sol=rmq[l][a];
    if(niv[sol]>niv[rmq[l][a+dif-(1<<l)]])
    sol=rmq[l][a+dif-(1<<l)];

    return sol;
}
int main()
{
    ifstream f("lca.in");

    f>>n>>m;
    for(i=2;i<=n;++i)
    {
        f>>t[i];
        a[t[i]].push_back(i);
    }
    df(1,1);
    lg[1]=0;
    for(i=2;i<=n;++i)
    lg[i]=lg[i>>1]+1;

    for(i=1;i<=nr;++i)
    rmq[0][i]=i;

    for(i=1;(1<<i)<nr;++i)
    for(j=1;j<nr-(1<<i);++j)
    {
        rmq[i][j]=rmq[i-1][j];
        if(niv[rmq[i][j]]>niv[ rmq[i-1][j+(1<<i-1)] ])
        rmq[i][j]=rmq[i-1][j+(1<<i-1)];
    }
   /* for(i=0;(1<<i)<nr;++i)
    {
        for(j=1;j<nr-(1<<i);++j)
        g<<b[rmq[i][j]]<<" ";
        g<<"\n";
    }*/
    while(m--)
    {
        f>>x>>y;
        g<<b[lca(x,y)]<<"\n";
    }
    return 0;
}