Cod sursa(job #1135664)

Utilizator toranagahVlad Badelita toranagah Data 8 martie 2014 10:43:52
Problema Atac Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
//Problem atac from Infoarena
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

#define mp make_pair

const int INF = 1 << 30;
const int MAX_N = 32100;
const int MAX_LOG = 17;

int N, M, P;
vector<pair<int, int>> graph[MAX_N];
bool visited[MAX_N];
int X, Y, Z, A, B, C, D;

int euler_node[4 * MAX_N];
int euler_depth[4 * MAX_N];
int euler_pos[MAX_N];
int num_euler;
int max_depth;

int rm[MAX_LOG][4 * MAX_N];
int lg2[4 * MAX_N];

int ancestor[MAX_LOG][MAX_N];
int min_up[MAX_LOG][MAX_N];

void read_input();
void solve();
void dfs(int node, int depth);
void cross_euler(int node, int depth);
void build_rm();
void build_ancestry();
int rmq(int a, int b);
int lca(int a, int b);
int query(int node, int anc);
int mod(long long n, int MOD);

int main() {
  read_input();
  solve();
  return 0;
}

void read_input() {
  fin >> N >> M >> P;

  for (int i = 2, x, c; i <= N; i += 1) {
    fin >> x >> c;
    graph[x].push_back(mp(i, c));
    graph[i].push_back(mp(x, c));
  }

  fin >> X >> Y >> A >> B >> C >> D;
}

void solve() {
  for (int l = 0; (1 << l) <= N; l += 1) {
    for (int i = 1; i <= N; i += 1) {
      min_up[l][i] = INF;
    }
  }

  num_euler = 0;
  max_depth = 0;
  dfs(1, 1);

  build_rm();
  build_ancestry();

  for (int i = 1; i <= M; i += 1) {
    int w = lca(X, Y);
    Z = (X == Y ? 0 : min(query(X, w), query(Y, w)));
    if (i > M - P)
      fout << Z << '\n';

    X = mod(1LL * A * X + B * Y, N) + 1;
    Y = mod(1LL * C * Y + D * Z, N) + 1;
  }
}

void dfs(int node, int depth) {
  visited[node] = true;
  max_depth = max(max_depth, depth);

  cross_euler(node, depth);

  for (auto next: graph[node]) {
    if (not visited[next.first]) {
      ancestor[0][next.first] = node;
      min_up[0][next.first] = next.second;

      dfs(next.first, depth + 1);
      cross_euler(node, depth);
    }
  }
}

inline void cross_euler(int node, int depth) {
  num_euler += 1;
  euler_pos[node] = num_euler;
  euler_node[num_euler] = node;
  euler_depth[num_euler] = depth;
  rm[0][num_euler] = node;
}

void build_rm() {
  lg2[1] = 0;
  for (int i = 2; i <= num_euler; i += 1)
    lg2[i] = lg2[i / 2] + 1;

  for (int i = 1; i <= num_euler; i += 1) {
    rm[0][i] = i;
  }

  for (int l = 1; (1 << l) <= num_euler; l += 1) {
    for (int i = 1; i + (1 << l) - 1 <= num_euler; i += 1) {
      rm[l][i] = rmq(rm[l - 1][i], rm[l - 1][i + (1 << (l - 1))]);
    }
  }
}

inline int rmq(int a, int b) {
  if (euler_depth[a] < euler_depth[b]) {
    return a;
  } else {
    return b;
  }
}

inline int lca(int a, int b) {
  a = euler_pos[a];
  b = euler_pos[b];
  if (a > b) swap(a, b);

  int l = lg2[b - a + 1];
  return euler_node[rmq(rm[l][a], rm[l][b - (1 << l) + 1])];
}

void build_ancestry() {
  for (int l = 1; (1 << l) <= max_depth; l += 1) {
    for (int i = 1; i <= N; i += 1) {
      ancestor[l][i] = ancestor[l - 1][ancestor[l - 1][i]];
      min_up[l][i] = min(min_up[l - 1][i], min_up[l - 1][ancestor[l - 1][i]]);
    }
  }
}

int query(int node, int anc) {
  int da = euler_depth[euler_pos[anc]];
  int dn = euler_depth[euler_pos[node]];
  if (dn <= da) return INF;

  int l = lg2[da - dn + 1];

  return min(min_up[l][node], query(ancestor[l][node], anc));
}

inline int mod(long long n, int MOD) {
  if (n < MOD) return n;
  if (n < 2 * MOD) return n - MOD;
  return n % MOD;
}