Cod sursa(job #2294145)

Utilizator AndreiDumitrescuAndrei Dumitrescu AndreiDumitrescu Data 1 decembrie 2018 22:51:17
Problema Lowest Common Ancestor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <fstream>
//#include "algo.h"
#include <vector>
#include <queue>
using namespace std;

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

int dp[30][100010], nivel[100100];
vector <vector <int>> tati;
int viz[100010] = {0};

int DFS(int nod, int nivel_actual)
{
  nivel[nod] = 0;
  queue<int> q;
  q.push(nod);
  while(!q.empty())
  {
      nod = q.front();
      q.pop();
      for(int i = 0; i < tati[nod].size(); i++)
      {
          q.push(tati[nod][i]);
          nivel[tati[nod][i]] = nivel[nod] + 1;
      }
  }

}

int query(int x, int y){

    while(nivel[x] > nivel[y])
        x = dp[0][x];
    while(nivel[y] > nivel[x])
        y = dp[0][y];
    if(x == y)
        return x;
    for(int bit = 12; bit >= 0; bit--)
    {
        if(bit != 0)
        {
            if(dp[bit][x] == dp[bit][y] && dp[bit - 1][x] != dp[bit - 1][y])
            {
                return query(dp[bit - 1][x], dp[bit - 1][y]);
            }
        }
        else
        {
            if(dp[bit][x] == dp[bit][y])
                return dp[bit][y];
        }

    }
}

void creez_tati(int nod, int anterior, vector <vector <int>> graph) {
   if(nod != 1) {
     tati[anterior].push_back(nod);
     dp[0][nod] = anterior;
   }
   viz[nod] = 1;
   for(int i = 0; i < graph[nod].size(); i++) {
     if(viz[graph[nod][i]] == 0) {
       creez_tati(graph[nod][i], nod,  graph);
     }
   }

}

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

  //std::vector<int> answers(queries.size(), 0);
  tati.resize(graph.size() + 10);
  creez_tati(1, 0, graph);
  DFS(1, 0);
  for(int j = 1; j < 12; j++){
    for(int i = 1; i < graph.size(); i++){
      dp[j][i] = dp[j - 1][dp[j - 1][i]];
    }
  }
  for(int i = 0; i < queries.size(); i++) {
      g << query(queries[i].first, queries[i].second) << '\n';
      //g << answers[i] << '\n';
  }
  //return answers;
}


int main() {
  int n, m;
  f >> n >> m;
  vector< vector<int>> graph;
  vector<pair<int, int>> queries;
  graph.resize(n + 1);
  queries.resize(m);
  for(int i = 2; i <= n; i++) {
    int x, y;
    f >> x;// >> y;
    graph[x].push_back(i);
    //graph[y].push_back(x);
  }
  for(int i = 0; i < m; i++) {
    int x, y;
    f >> x >> y;
    queries[i] = make_pair(x, y);
  }
  lca(graph, queries);
}