Cod sursa(job #2475006)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 16 octombrie 2019 01:27:46
Problema Lowest Common Ancestor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");

int E[200005],L[200005], Oc[100005], M[100005][20],Min_node[100005][20];
int nr,n,q,i,x;
vector<int> A[100005];

int log(int n)
{
    int p = 1;
    int nr = 0;
    while(p<=n)
    {
        nr++;
        p*=2;
    }
    return nr;
}

void dfs(int nod, int level)
{
    nr++;
    if(Oc[nod] == 0)
        Oc[nod] = nr;
    E[nr] = nod;
    L[nr] = level;
    for(int x:A[nod])
    {
        dfs(x,level+1);
        nr++;
        E[nr] = nod;
        L[nr] = level;

    }
}

void preproc_rmq()
{
    int i,j;
    for(i=1;i<=2*n-1;i++){
        Min_node[i][0] = E[i];
        M[i][0] = L[i];
    }
    for(j=1;(1<<j) <=2*n-1;j++)
    {
        for(i=1; i + (1<<(j-1)) - 1 <=2*n-1; i++){
            M[i][j] = M[i][j-1];
            Min_node[i][j] = Min_node[i][j-1];
            if(M[i][j] > M[i+(1<<(j-1)) -1][j-1])
            {
                M[i][j] = M[i+(1<<(j-1)) -1][j-1];
                Min_node[i][j] = Min_node[i+(1<<(j-1)) -1][j-1];
            }
        }
    }
}

int rmq(int l, int r)
{
    l = Oc[l];
    r = Oc[r];
    int len = log(r-l+1);
    if(M[l][len]<= M[r-(1<<len)+1][len])
        return Min_node[l][len];
    else
        return Min_node[r-(1<<len)+1][len];
}

int main()
{
    f>>n>>q;
    for(i=1;i<=n-1;i++)
    {
        f>>x;
        A[x].push_back(i+1);
    }
    dfs(1,0);
    preproc_rmq();
    int l,r;
    int j;

    for(i=1;i<=q;i++){
        f>>l>>r;
        g<<rmq(l,r)<<'\n';
    }


    return 0;
}