Cod sursa(job #2409657)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 19 aprilie 2019 12:33:18
Problema Lowest Common Ancestor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>
using namespace std;

class InputReader
{
private:

  static const int SIZE = 1 << 12;
  char buf[SIZE]; int ptx;

  FILE *inFile;

  inline void advance (void)
  {
    if (++ptx == SIZE) {
      ptx = 0; fread(buf, SIZE, 1, inFile); }
  }

  inline char current (void)
  {
    return buf[ptx];
  }

public:

  InputReader (const char *fileName)
  {
    inFile = fopen(fileName, "r"); ptx = 0;
    fread(buf, SIZE, 1, inFile);
  }

  InputReader &operator >> (int &val)
  {
    val = 0;
    while (current() < '0' || current() > '9') {
      advance(); }
    while (current() >= '0' && current() <= '9') {
      val = val * 10 + (current() - '0');
      advance(); }
    return *this;
  }
} in("lca.in");
ofstream out("lca.out");

const int DIM = 100005;
const int LOG = 17;

int anc[DIM][LOG], lev[DIM];
vector<int> edg[DIM];

void dfs (int x)
{
  for (int i = 1; i < LOG; ++i) {
    anc[x][i] = anc[anc[x][i - 1]][i - 1]; }
  for (int y : edg[x]) {
    lev[y] = lev[x] + 1; anc[y][0] = x; dfs(y); }
}

int lca (int x, int y)
{
  if (lev[x] > lev[y]) {
    swap(x, y); }
  for (int i = LOG - 1; i >= 0; --i) {
    if (lev[y] - (1 << i) >= lev[x]) {
      y = anc[y][i]; } }
  for (int i = LOG - 1; i >= 0; --i) {
    if (anc[x][i] != anc[y][i]) {
      x = anc[x][i], y = anc[y][i]; } }
  if (x == y) {
    return x; }
  else {
    return anc[x][0]; }
}

int main (void)
{
  int n, q; in >> n >> q;
  for (int i = 2; i <= n; ++i) {
    int x; in >> x;
    edg[x].push_back(i); }
  dfs(1);
  while (q--) {
    int x, y; in >> x >> y;
    out << lca(x, y) << "\n"; }
  return 0;
}