Cod sursa(job #1464418)

Utilizator jul123Iulia Duta jul123 Data 23 iulie 2015 14:57:36
Problema Lowest Common Ancestor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int> >e;
vector<int>v[100005];
int tata[100005], lg[100005], first[100005];
pair<int, int> dp[100005][20];

void Euler(int nod, int level) {
    e.push_back(make_pair(level, nod));
    for(int i = 0; i < v[nod].size(); ++i) {
        Euler(v[nod][i], level + 1);
        e.push_back(make_pair(level, nod));
    }
}
int main()
{
    int n, m, x, y;
    FILE *fin = fopen("lca.in", "r");
    FILE *fout = fopen("lca.out", "w");

    fscanf(fin, "%d %d", &n, &m);

    for(int i = 2; i <= n; ++i)
        lg[i] = lg[i / 2] + 1;

    for(int i = 1; i < n; ++i) {
        fscanf(fin, "%d", &x);
        --x;
        tata[i] = x;
        v[x].push_back(i);
    }
    Euler(0, 1);
    for(int i = 0; i < e.size(); ++i)
        if(first[e[i].second] == 0)
            first[e[i].second] = i;
    for(int i = 0; i < e.size(); ++i) {
        dp[i][0] = e[i];
        //cout << e[i].second + 1<<" ";
    }
    //cout << "\n";
    for(int j = 1; j < 20; ++j)
        for(int i = 0; i < e.size(); ++i)
            if(i + (1 << (j - 1)) <= e.size())
                dp[i][j] = min(dp[i + (1 << (j - 1))][j - 1], dp[i][j - 1]);

    for(int i = 0; i < m; ++i) {
        fscanf(fin, "%d %d", &x, &y);
        --x;
        --y;
        int c = first[x], b = first[y];
        if(c > b) {
            int aux = c;
            c = b;
            b = aux;
        }
       // cout << b << " "<<c << " ";
        int x = lg[b - c + 1];
       // cout << dp[c][x].second <<" "<< dp[b - (1 << x) + 1][x].second << "\n";
        fprintf(fout, "%d\n", min(dp[c][x], dp[b - (1 << x) + 1][x]).second + 1);
    }
}