Cod sursa(job #2179204)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 20 martie 2018 00:04:52
Problema Lowest Common Ancestor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");
int i,n,t,doi[2*NMAX],x,y,p[NMAX],d,nr,m;
vector <int> G[NMAX];
struct du{
    int n,m;}rmq[2*NMAX][20];
void dfs(int nod,int nivel){
    rmq[++nr][0].m=nivel;
    rmq[nr][0].n=nod;
    if(!p[nod])
        p[nod]=nr;
    for(int i=0;i<G[nod].size();i++){
        dfs(G[nod][i],nivel+1);
        rmq[++nr][0].n=nod;
        rmq[nr][0].m=nivel;
    }

}
void pre(){
    for(i=1;i<=nr;i++){
        t=i;
        while(t>=2){
            doi[i]++;
            t/=2;
        }
    }
}
void RMQ(){
    for(int j=1;j<=doi[nr];j++){
            int a=1;
        for(i=1;i+(1<<j)-1<=nr;i++)
            if(rmq[i][j-1].m>rmq[i+(1<<(j-1))][j-1].m){
                rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
            }
            else
                rmq[i][j]=rmq[i][j-1];

    }
}
int main()
{
    f>>n>>m;
    for(i=2;i<=n;i++){
        f>>x;
        G[x].push_back(i);
    }
    dfs(1,1);
    pre();
    RMQ();
    for(i=1;i<=m;i++){
        f>>x>>y;
        if(p[x]>p[y])
            swap(x,y);
        d=doi[p[y]-p[x]+1];
        if(rmq[p[x]][d].m<rmq[p[y]-(1<<d)+1][d].m)
            g<<rmq[p[x]][d].n<<'\n';
        else
            g<<rmq[p[y]-(1<<d)+1][d].n<<'\n';
    }
    return 0;
}