Cod sursa(job #2293794)

Utilizator AndreiDumitrescuAndrei Dumitrescu AndreiDumitrescu Data 1 decembrie 2018 16:25:43
Problema Lowest Common Ancestor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.63 kb
#include <fstream>

#include <iostream>

#include <vector>

#define infinit 999999999



using namespace std;



ifstream f("lca.in");

ofstream g("lca.out");



vector<vector <int>> graph;

vector<pair<int, int>> queries;

vector<int> answers;



int parcurgere_euleriana(int nod, int nivel_actual, vector<vector<int>> vecini, vector<int>  &parcurgere, vector<int>  &nivel, vector<int>  &prima, vector<int>  &viz, int &k)

{

    parcurgere[k] = nod;

    nivel[k] = nivel_actual;

    if(viz[nod] == 0)

    {

        prima[nod] = k;

        viz[nod] = 1;

    }

    k++;

    for(int i = 0; i < vecini[nod].size(); i++)

    {

      if(viz[vecini[nod][i]] == 0) {

        parcurgere_euleriana(vecini[nod][i], nivel_actual + 1, vecini, parcurgere, nivel, prima, viz, k);

        parcurgere[k] = nod;

        nivel[k] = nivel_actual;

        k++;

      }

    }

    return 0;

}







int minim(int a, int b, vector<int>  nivel)

{

  if(a == infinit)

    return b;

  if(b == infinit)

    return a;

  if(nivel[a] < nivel[b])

        return a;

  return b;

}



int minim_corect(int a, int b, int x, int y)

{



    if(a < b)

        return x;

    return y;

}



int interogare(int x, int y, vector<vector <int>>dp, vector<int> log, vector<int> nivel)

{

    if(x == y)

      return x;

    else

    {

      int dif;

      dif = y - x ;

      //return minim(dp[x][log[dif]], dp[y-(1<<log[dif])][log[dif]], nivel);
      if(nivel[dp[x][log[dif]]] < nivel[dp[y-(1<<log[dif])][log[dif]]])
          return dp[x][log[dif]];
      else
          return dp[y-(1<<log[dif])][log[dif]];
    }

}





void lca(const std::vector<std::vector<int>>& graph, const std::vector< std::pair<int, int> >& queries) {

    // TODO

  //  std::vector<std::vector<int> > tati(graph.size());

    //creare_tati(1, graph, 0);



    //int dp[400010][22]  , log[400010] ;

    vector<int> log;

    vector<int> parcurgere;

    vector<int> prima;

    vector<int> viz;

    vector<int> nivel;

    log.resize(4*graph.size() + 10);

    parcurgere.resize(4*graph.size() + 10);

    prima.resize(4*graph.size() + 10);

    viz.resize(graph.size() + 10);

    nivel.resize(4*graph.size() + 10);

    int k = 1;

    vector<vector <int>>dp;

    parcurgere_euleriana(1, 0, graph, parcurgere, nivel, prima, viz, k);

    dp.resize(4*graph.size() + 10);

    for(int i = 0 ; i < 4*graph.size() + 10; i++)

      dp[i].resize(30);



    //std::vector<int> answers(queries.size(), 0);

    for(int i = 1; i <= k; i++)

        dp[i][0] = minim_corect(nivel[i], nivel[i+1], i, i+1);

    dp[k][0] = parcurgere[k];

    for(int i = 2; i <= k; i++)

        log[i] = log[i/2] + 1;

    for(int j = 1; j <= log[k]; j++)

        for(int i = 1;(i + (1 << (j-1))) <= k ; i++)

            dp[i][j] = minim(dp[i][j-1], dp[i  + (1 << (j-1))][j-1], nivel);

    for(int i = 0; i < queries.size(); i++)

    {

        if(prima[queries[i].first] < prima[queries[i].second])

            g << parcurgere[interogare(prima[queries[i].first], prima[queries[i].second], dp, log, nivel)] << '\n';

        else

            g <<  parcurgere[interogare(prima[queries[i].second], prima[queries[i].first], dp, log, nivel)] << '\n' ;

    }


  //  return answers;

}













int main(){

    int n, m;

    f >> n >> m;

    graph.resize(n+1);

    queries.resize(m);

    answers.resize(m);

    for(int i = 2; i <= n; i++){

      int x, y;

      f >> x ;

      //f >> x;

      //graph[x].push_back(i);

      //graph[y].push_back(x);

      graph[x].push_back(i);

    }

    for(int i = 0; i < m; i++){

      int x, y;

      f >> x >> y;



      queries[i] = make_pair(x, y);

    }

    lca(graph, queries);



    return 0;

}