Cod sursa(job #2355876)

Utilizator DavidLDavid Lauran DavidL Data 26 februarie 2019 12:59:48
Problema Lowest Common Ancestor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("lca.in");
ofstream fo("lca.out");

const int NMAX = 1e5 + 5;
const int LOG = 25;

struct multe
{
    int val, poz;
};

vector <int> G[NMAX];
int p[NMAX], niv[NMAX];
int n;
vector <int> repr;
multe rmq[LOG][2 * NMAX];

void dfs(int nod)
{
    repr.push_back(nod);
    for (auto v: G[nod])
    {
        niv[v] = niv[nod] + 1;
        dfs(v);
    }
}

void getRmq()
{
    int m = repr.size();
    for (int j = 0; j < m; j++)
        rmq[0][j] = {niv[repr[j]], repr[j]};

    for (int i = 1; (1 << i) <= m; i++)
    {
        for (int j = 0; j < m; j++)
            if (j + (1 << i) - 1 < m) /// intra
            {
                if (rmq[i - 1][j].val > 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 main()
{
    fi >> n;
    for (int i = 2; i <= n; i++)
    {
        fi >> p[i];
        G[p[i]].push_back(i);
    }

    dfs(1);

    getRmq();

    return 0;
}