Cod sursa(job #2797495)

Utilizator casiannCasian casiann Data 9 noiembrie 2021 23:54:05
Problema Lowest Common Ancestor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream fin("lca.in");
ofstream fout("lca.out");
 
#define MAXN 100001
#define MAXLOGN 20
 
int n, m, nodes[2*MAXN+1], depth[2*MAXN+1], last[MAXN], current_position = 1, a[2*MAXN+1][MAXLOGN], Lg[2*MAXN+1];
vector<vector<int>> children;
 
void pre_process_rmq(){
    for(int i=2; i< current_position; i++)
        Lg[i] = Lg[i>>1] + 1;
    for(int i=1; i<current_position; i++)
        a[i][0] = i;
    for(int j=1; j<=MAXLOGN; j++)
        for(int i=1; i<= current_position - (1<<j) + 1; i++){
            if(depth[a[i][j-1]] < depth[a[i+(1<<(j-1))][j-1]])
                a[i][j] = a[i][j-1];
            else a[i][j] = a[i+(1<<(j-1))][j-1];
        }
}
 
void citire(){
    fin >> n >> m;
    children = vector<vector<int>> (n+1);
    for(int i=1; i<n; i++){
        int father;
        fin >> father;
        children[father].push_back(i+1);
    }
}
 
void dfs(int node, int node_depth){
    nodes[current_position] = node;
    depth[current_position] = node_depth;
    last[node] = current_position;
    current_position++;
    for(auto child: children[node]){
        dfs(child, node_depth + 1);
        nodes[current_position] = node;
        depth[current_position] = node_depth;
        last[node] = current_position;
        current_position++;
    }
}
 
int main(){
    citire();
    // EULERIAN TOUR
    dfs(1, 0);
    // nodes[] -> nodes from Eulerian Tour
    // depth[] -> depth for each node of nodes[]
    // last[]  -> last position of each node in Eulerian Tour
    pre_process_rmq();
    for(int ind = 1; ind<=m; ind++){
        int node_st, node_dr, st, dr, length, logg;
        fin >> node_st >> node_dr;
        st = last[node_st], dr = last[node_dr];
        if(st > dr) swap(st,dr);
        length = dr-st+1;
        logg = Lg[length];
        if(depth[a[st][logg]] < depth[a[dr-(1<<logg)+1][logg]])
            fout << nodes[a[st][logg]] << '\n';
        else fout << nodes[a[dr-(1<<logg)+1][logg]] << '\n';
    }
    return 0;
}