Cod sursa(job #2294997)

Utilizator AndreiDumitrescuAndrei Dumitrescu AndreiDumitrescu Data 2 decembrie 2018 23:46:20
Problema Lowest Common Ancestor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.79 kb
#include <fstream>
#include "algo.h"
#include <vector>
#include <queue>
#define infinit 999999999

using namespace std;

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




int parcurgere[4000010], nivel[4000010], prima[1000010], viz[1000010];
int dp[4000010][40], log[4000010];
std::vector < std::vector<int>> vecini;
int k = 1;
int parcurgere_euleriana(int nod, int nivel_actual)
{
    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);
        parcurgere[k] = nod;
        nivel[k] = nivel_actual;
        k++;
      }
    }
    return 0;
}

int minim(int a, int b)
{
  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)
{
    if(x == y)
      return x;
    else
    {
      int dif;
      dif = y - x ;
      return minim(dp[x][log[dif]], dp[y-(1<<log[dif])][log[dif]]);
    }
}

std::vector<int> lca(const std::vector<std::vector<int>>& graph, const std::vector< std::pair<int, int> >& queries) {
    // TODO
    vecini.resize(graph.size());
    std::vector <int> answers;
    answers.resize(queries.size());
    for(int i = 1; i < graph.size(); i++) {
      for(int j = 0; j < graph[i].size(); j++) {
          vecini[i].push_back(graph[i][j]);
      }
    }
    parcurgere_euleriana(1, 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]);
    for(int i = 0; i < queries.size(); i++)
    {
        int x = queries[i].first;
        int y = queries[i].second;
        if(prima[x] < prima[y])
            answers[i] = parcurgere[interogare(prima[x], prima[y])] ;
        else
            answers[i] = parcurgere[interogare(prima[y], prima[x])];

    }
    return answers;
  //  return std::vector<int>();
}

int main() {
  vector<vector <int>> graph;
  vector<pair<int, int>> queries;
  vector<int> answers;
  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 >> y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
  for(int i = 0; i < m; i++) {
    int x, y;
    f >> x >> y;
    queries[i] = make_pair(x, y);
  }
  answers = lca(graph, queries);
  for(int i = 0; i < m; i++) {
     g << answers[i] << '\n';
  }
}