Cod sursa(job #2331532)

Utilizator racheriunicolaechowchow racheriunicolae Data 29 ianuarie 2019 17:55:48
Problema Lowest Common Ancestor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1e5;
vector <int > e , l , g[NMAX];
int h[NMAX], viz[NMAX];
void dfs(int node , int lvl)
{
    e.push_back(node);
    l.push_back(lvl);
    h[node] = e.size() - 1;
    viz[node] = 1;
    for(int i = 0; i < g[node].size(); i++)
        if(!viz[g[node][i]])
        {
            dfs(g[node][i] , lvl + 1);
            e.push_back(node);
            l.push_back(lvl);
        }

}
int n , m , i , x , dp[40][NMAX] , p , u , v;
int main()
{
    ifstream fin("lca.in");
    ofstream fout("lca.out");
    fin >> n >> m;
    e.push_back(0);
    l.push_back(0);
    for(i = 1; i < n; i++)
    {
        fin >> x;
        g[x].push_back(i + 1);
        g[i + 1].push_back(x);
    }
    dfs(1 , 1);
    for(i = 1; i < e.size(); i++)
        dp[0][i] = i;

    for(p = 1; (1 << p) < e.size(); p++)
    {
        for(i = 1; i + (1<<p) - 1 < e.size(); i++)
        {
            if(l[dp[p-1][i]] < l[dp[p - 1][i + (1 << (p-1))]])
                dp[p][i] = dp[p - 1][i];
            else dp[p][i] = dp[p - 1][i + (1 << (p - 1))];

        }
    }
    while(m)
    {
        m--;
        fin >> u >> v;
        if(h[u] > h[v])swap(u , v);
        int k = h[v] - h[u] + 1;
        k = log2(k);
        if(l[dp[k][h[u]]] < l[dp[k][h[v] - (1 << k) + 1]])
            fout << e[dp[k][h[u]]]<<"\n";
        else fout << e[dp[k][h[v] - (1 << k) + 1]]<<"\n";

    }
    return 0;
}