Cod sursa(job #1946878)

Utilizator preda.andreiPreda Andrei preda.andrei Data 30 martie 2017 16:06:19
Problema Lowest Common Ancestor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <forward_list>
#include <fstream>
#include <vector>

using namespace std;

struct Node
{
    int position;
    int level;
    forward_list<int> edges;
};

using Tree = vector<Node>;

template <class T>
using Matrix = vector<vector<int>>;

void Euler(Tree &t, int node, vector<int> &res)
{
    res.push_back(node);
    t[node].position = res.size() - 1;

    for (int next : t[node].edges) {
        t[next].level = t[node].level + 1;
        Euler(t, next, res);
        res.push_back(node);
    }
}

vector<int> Dfs(Tree &t, int root)
{
    t[root].level = 0;
    vector<int> euler;
    Euler(t, root, euler);
    return euler;
}

Matrix<int> RmqPrecalc(Tree &t, int root)
{
    auto euler = Dfs(t, root);
    Matrix<int> rmq(euler.size(), vector<int>(20, -1));

    for (unsigned i = 0; i < euler.size(); ++i) {
        rmq[i][0] = euler[i];
    }

    for (int p = 1; p < 20; ++p) {
        for (int i = euler.size() - 1; i - (1 << p) + 1 >= 0; --i) {
            int a = rmq[i][p - 1];
            int left = i - (1 << p) + 1;
            int b = rmq[left + (1 << (p - 1)) - 1][p - 1];

            rmq[i][p] = (t[a].level < t[b].level) ? a : b;
        }
    }
    return rmq;
}

int FindLca(const Tree &t, const Matrix<int> &rmq, int x, int y)
{
    x = t[x].position;
    y = t[y].position;
    if (x > y) {
        swap(x, y);
    }

    int len = y - x + 1;
    int pow = 0;

    while ((1 << pow) <= len) {
        ++pow;
    }
    --pow;

    int a = rmq[y][pow];
    int b = rmq[x + (1 << pow) - 1][pow];
    return (t[a].level < t[b].level) ? a : b;
}

int main()
{
    ifstream fin("lca.in");
    ofstream fout("lca.out");

    int n, q;
    fin >> n >> q;

    Tree tree(n);
    for (int i = 1; i < n; ++i) {
        int fa;
        fin >> fa;
        tree[fa - 1].edges.push_front(i);
    }

    auto rmq = RmqPrecalc(tree, 0);

    while (q--) {
        int x, y;
        fin >> x >> y;
        fout << FindLca(tree, rmq, x - 1, y - 1) + 1 << "\n";
    }

    return 0;
}