Cod sursa(job #2572064)

Utilizator vladadAndries Vlad Andrei vladad Data 5 martie 2020 11:27:15
Problema Lowest Common Ancestor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define sc second
using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");
int n, m, a, b, q;
int euler[100001];
int rmq[35][100001];
int nivel[100001];
int lst[100001];
int lg[2000001];
int lvl[100001];
vector<int>v[100001];
void dfs(int nod)
{
    m++;
    euler[m]=nod;
    nivel[m]=lvl[nod];
    for(int i=0; i<v[nod].size(); i++)
    {
        lvl[v[nod][i]]=lvl[nod]+1;
        dfs(v[nod][i]);
        m++;
        euler[m]=nod;
        nivel[m]=lvl[nod];
    }
    lst[nod]=m;
}
void build()
{
    for(int i=2; i<=m; i++)
        lg[i]=lg[i/2]+1;
    for(int i=1; i<=m; i++)
        rmq[0][i]=i;
    for(int i=1; i<=lg[m]; i++)
    {
        for(int j=1; j+(1<<i)-1<=m; j++)
        {
            if(nivel[rmq[i-1][j]]<nivel[rmq[i-1][j+(1<<(i-1))]])
               rmq[i][j]=rmq[i-1][j];
            else
                rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
        }
    }
}
int LCA(int x, int y)
{
    int a=min(lst[x], lst[y]);
    int b=max(lst[x], lst[y]);
    int ln=lg[b-a+1];
    int ans=rmq[ln][a];
    if(nivel[rmq[ln][b-(1<<ln)+1]]<nivel[ans])
        ans=rmq[ln][b-(1<<ln)+1];
    return euler[ans];
}
int main()
{
    f>>n>>q;
    for(int i=2; i<=n; i++)
    {
        int x;
        f>>x;
        v[x].push_back(i);
    }
    dfs(1);
    build();
    for(; q; q--)
    {
        f>>a>>b;
        g<<LCA(a, b)<<'\n';
    }
    return 0;
}