Cod sursa(job #1513185)

Utilizator rumburakrumburak rumburak Data 29 octombrie 2015 06:55:39
Problema Lowest Common Ancestor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N = 100001, L = 18;

ifstream in("lca.in");
ofstream out("lca.out");

int n, q, t[N], ne, e[2*N], nivel[N], r[2*N][L], log[2*N], poz[N];
int lst[N], fiu[N], urm[N], nr;

void adauga(int x, int y)
{
    nr++;
    fiu[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void citire()
{
    in >> n >> q;
    for (int i = 2; i <= n; i++)
    {
        in >> t[i];
        adauga(t[i], i);
    }
}

void euler(int x)
{
    nivel[x] = 1 + nivel[t[x]];
    e[++ne] = x;
    int p, y;
    p = lst[x];
    while (p != 0)
    {
        y = fiu[p];
        euler(y);
        e[++ne] = x;
        p = urm[p];
    }
    poz[x] = ne;
}

void scrieEuler()
{
    int i;
    out << ne << "\n";
    for (i = 1; i < 2*n; i++)
        out << e[i] << "\t";
    out << "\n";
    for (i = 1; i < 2*n; i++)
        out << nivel[e[i]] << "\t";
    out << "\n";
    for (i = 1; i <= n; i++)
        out << poz[i] << "\t";
}

void calculLog()
{
    int p = 0;
    for (int i = 1; i <= ne; i++)
    {
        if (i == (1 << p)) p++;
        log[i] = p - 1;
        //out << log[i] << "\n";
    }
}

void constructieRmq()
{
    int i, j;
    calculLog();
    for (i = 1; i <= ne; i++)
    {
        r[i][0] = e[i];
        for (j = 1; (1 << j) <= i; j++)
        {
            r[i][j] = r[i][j - 1];
            if (nivel[r[i - (1 << (j - 1))][j - 1]] < nivel[r[i][j]])
                r[i][j] = r[i - (1 << (j - 1))][j - 1];
        }
    }
}

void schimb(int &x, int &y)
{
    int aux = x;
    x = y;
    y = aux;
}

int raspuns(int x, int y)
{
    if (x > y) schimb(x, y);
    int lung = y - x + 1, rez;
    rez = r[y][log[lung]];
    if (nivel[r[x + (1 << log[lung]) - 1][log[lung]]] < nivel[rez])
        rez = r[x + (1 << log[lung]) - 1][log[lung]];
    return rez;
}

void raspunde()
{
    int i, x, y;
    for (i = 0; i < q; i++)
    {
        in >> x >> y;
        out << raspuns(poz[x], poz[y]) << "\n";
    }
}

int main()
{
    citire();
    nivel[0] = -1;
    euler(1);
    //scrieEuler();
    constructieRmq();
    raspunde();
    in.close();
    out.close();
    return 0;
}