Cod sursa(job #945089)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 30 aprilie 2013 15:12:55
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<cmath>
#include<cassert>
#include<fstream>
#include<vector>
#include<algorithm>

#define VALOARE 900001

using namespace std;

const int knmax = 32005;

int lsb(int &x){
  return x & -x;
}

int n, m, p, a, b, c, d, st, fin, val[knmax], dad[knmax];
vector<int> graph[knmax];

void read(){
  ifstream in("atac.in");

  in >> n >> m >> p;

  val[1] = VALOARE;

  for(int i = 2; i <= n; ++i){
    in >> dad[i] >> val[i];
    graph[dad[i]].push_back(i);
  }

  in >> st >> fin >> a >> b >> c >> d;
}

int lvl, level[knmax], p2[knmax * 2], anc[17][knmax], dp[17][knmax];

void dfs(int x){
  level[x] = lvl;
  ++lvl;
  for(int i = 0; i < graph[x].size(); ++i)
    dfs(graph[x][i]);
  --lvl;
}

void precomp(){
  dfs(1);

  p2[0] = -1;
  for(int i = 1; i <= knmax * 2; ++i)
    p2[i] = p2[i >> 1] + 1;

  for(int i = 1; i <= n; ++i){
    anc[0][i] = dad[i];
    dp[0][i] = val[i];
  }

  for(int i = 1; i < 16; ++i)
    for(int j = 1; j <= n; ++j){
      dp[i][j] = min(dp[i - 1][j], dp[i - 1][anc[i - 1][j]]);
      anc[i][j] = anc[i - 1][anc[i - 1][j]];
    }
}

int ancestor(int x, int up){
  up = fabs(up);
  if(up == 0)
    return x;
  return ancestor(anc[p2[lsb(up)]][x], up - lsb(up));
}

int lca(int x, int y){
  if(level[x] > level[y])
    swap(x, y);
  x = ancestor(x, level[y] - level[x]);

  int left = 0, right = level[x], mid, last;
  while(left <= right){
    mid = (left + right) >> 1;
    if(ancestor(x, mid) == ancestor(y, mid)){
      last = mid;
      right = mid - 1;
    }
    else
      left = mid + 1;
  }

  return ancestor(x, last);
}

int way(int x, int up){
  up = fabs(up);
  if(up == 0)
    return VALOARE;
  return min(dp[p2[lsb(up)]][x], way(anc[p2[lsb(up)]][x], up - lsb(up)));
}

vector<int> ans;

void solve(){
  precomp();

  int t = m;

  do{
    --t;

    if(st == fin)
      ans.push_back(0);
    else{
      int mid = lca(st, fin);
      assert(mid >= 0 && mid <= n);
      int x = way(st, level[mid] - level[st]), y = way(fin, level[mid] - level[fin]);
      ans.push_back(min(x, y));
    }

    st = ((long long)st * a + (long long)fin * b) % n + 1;
    fin = ((long long)fin * c + (long long)ans.back() * d) % n + 1;
  }while(t);

}

void write(){
  ofstream out("atac.out");

  for(int i = m - p; i < m; ++i)
    out << ans[i] << "\n";
}

int main(){
  read();
  solve();
  write();

  return 0;
}