Cod sursa(job #2305852)

Utilizator mirunaFmiruna mirunaF Data 21 decembrie 2018 11:37:27
Problema Lowest Common Ancestor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>

//#define for(n) for(int i = 1 ; i <= n; i++)

using namespace std;

void init ( int n, bool *w)
{
    for (int i = 1; i <= n; i++)
        w[i] = false;
}

int main()
{
    int n, m, i, *v, x, y;
    bool *w;

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

    in >> n >> m;
    v = new int [n+2];
    w = new bool [n+2];
    for ( i = 2; i <= n ; i++)
        in >> v[i];
    v[1] = 0;
//    cout << "vector : ";
//    for ( n )
//        cout << v[i] << " ";
//    cout << endl;
    for( i = 1; i <= m; i++)
    {
        init (n , w);
        in >> x >> y;
        int j = x;
        while ( j != 0){
            w[j] = true;
//            cout << j << " ";
            j = v[j];
        }
//        cout << endl;
        j  = y;
        while ( w[j] != true)
           j = v[j];
        out << j << "\n";
    }

    in.close();
    out.close();

    return 0;
}