Cod sursa(job #473849)

Utilizator mlazariLazari Mihai mlazari Data 1 august 2010 10:54:52
Problema Lowest Common Ancestor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<fstream>
#include<vector>

using namespace std;

#define NMAX 100003

ifstream fi("lca.in");

vector<int> f[NMAX],euler;
int poz[NMAX],niv[NMAX],rmq[20][NMAX<<1],log[NMAX<<1],d[20];
int n,m,x,i,a,b,aux1,aux2,ne;

void Euler(int nod, int nv) {
  int i,s;
  poz[nod]=ne++;
  euler.push_back(nod);
  niv[nod]=nv;
  for(i=0,s=f[nod].size();i<s;i++) {
    Euler(f[nod][i],nv+1);
    euler.push_back(nod);
    ++ne;
  }
}

void calcD() {
  d[0]=1;
  for(int i=1;i<20;i++) d[i]=d[i-1]<<1;
}

void calcLog() {
  int i,j=1,s=ne;
  int dj=d[j];
  for(i=1;i<s;i++) {
    if(i==dj) {
      j++;
      dj=d[j];
    }
    log[i]=j-1;
  }
}

void preRMQ() {
  int i,j,s=ne,aux1,aux2;
  for(i=0;i<s;i++) rmq[0][i]=euler[i];
  for(i=1;d[i]<=s;i++)
   for(j=0;j<=s-d[i];j++) {
     aux1=rmq[i-1][j];
     aux2=rmq[i-1][j+d[i-1]];
     if(niv[aux1]<niv[aux2])
      rmq[i][j]=aux1;
     else rmq[i][j]=aux2;
   }
}

int RMQ(int a, int b) {
  int aux1=log[b-a+1];
  int aux2=rmq[aux1][a];
  int best=aux2;
  a+=d[aux1];
  while(a<=b) {
    aux1=log[b-a+1];
    aux2=rmq[aux1][a];
    if(niv[aux2]<niv[best]) best=aux2;
    a+=d[aux1];
  }
  return best;
}

int main() {
  fi>>n>>m;
  for(i=2;i<=n;i++) {
    fi>>x;
    f[x].push_back(i);
  }
  Euler(1,1);
  calcD();
  calcLog();
  preRMQ();
  freopen("lca.out","w",stdout);
  while(m--) {
    fi>>a>>b;
    aux1=poz[a];
    aux2=poz[b];
    if(aux1>aux2) swap(aux1,aux2);
    printf("%d\n",RMQ(aux1,aux2));
  }
  return 0;
}