Cod sursa(job #2192578)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 6 aprilie 2018 16:21:27
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.73 kb
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

template<typename T>
class Rmq {
 public:
  Rmq() {}

  template<typename Array>
  Rmq(int size, const Array& array) : Rmq(size, array, vector<int>()) {}

  template<typename Array>
  Rmq(int size, const Array& array, const vector<int>& key) : size_(size),
    key_(key) {
    lg_max_ = GetLog(size);
    rmq_.resize(lg_max_);
    for (int i = 0; i < (int)rmq_.size(); i++) {
      rmq_[i].resize(size_);
    }
    PrecalculateLog();
    Build(array);
  }

  T Get(int x, int y) {
    int lg = lg_[y - x + 1];
    return GetMin(rmq_[lg][x], rmq_[lg][y - (1 << lg) + 1]);
  }

 private:
  int size_;
  int lg_max_;
  vector<int> lg_;
  vector<vector<T>> rmq_;
  vector<int> key_;

  int GetLog(int size) {
    int lg = 1;
    while (size) {
      lg++;
      size /= 2;
    }
    return lg;
  }

  void PrecalculateLog() {
    lg_.resize(size_ + 1);
    lg_[1] = 0;
    for (int i = 2; i <= size_; i++) {
      lg_[i] = lg_[i / 2] + 1;
    }
  }

  template<typename Array>
  void Build(Array & array) {
    for (int i = 0; i < size_; i++) {
      rmq_[0][i] = array[i];
    }
    for (int i = 1, p = 2; p <= size_; i++, p *= 2)
      for (int j = 0; j + p - 1 < size_; j++) {
        rmq_[i][j] = GetMin(rmq_[i - 1][j], rmq_[i - 1][j + p / 2]);
      }
  }

  int GetMin(int x, int y) {
    if (Key(x) < Key(y)) {
      return x;
    }
    return y;
  }

  // If you want the RMQ to be compared with a different key, modify this
  int Key(int x) {
    if (key_.empty()) {
      return x;
    }
    return key_[x];
  }
};

class Tree {
 public:
  Tree(int num_vertices, int root) : num_vertices_(num_vertices), root_(root) {
    neighbors_.resize(num_vertices_ + 1);

    log_.resize(num_vertices_ + 1);
    for (int i = 2; i <= num_vertices; i++) {
      log_[i] = log_[i / 2] + 1;
    }

    father_.resize(log_[num_vertices]);
    min_.resize(log_[num_vertices]);

    for (int i = 0; i < static_cast<int>(father_.size()); i++) {
      father_[i].resize(num_vertices + 1);
      min_[i].resize(num_vertices + 1);
    }
  }

  void AddEdge(int x, int y, int z) {
    neighbors_[x].push_back({y, z});
    neighbors_[y].push_back({x, z});
  }

  void Precalculate() {
    first_apparition_.resize(num_vertices_ + 1, -1);
    level_.resize(num_vertices_ + 1, 0);
    DfsEuler(root_);
    rmq_ = Rmq<int>(euler_path_.size(), euler_path_, level_);
    PrecalculateAncestors();
  }

  int GetLCA(int x, int y) {
    x = first_apparition_[x];
    y = first_apparition_[y];

    if (x > y) {
      swap(x, y);
    }

    return rmq_.Get(x, y);
  }

  int GetMin(int x, int y) {
    if (x == y) {
      return 0;
    }

    int lca = GetLCA(x, y);
    return min(GetMinWithLCA(x, lca), GetMinWithLCA(y, lca));
  }

 private:
  int num_vertices_;
  int root_;
  vector<vector<pair<int, int>>> neighbors_;
  vector<int> euler_path_;
  vector<int> first_apparition_;
  vector<int> level_;
  Rmq<int> rmq_;

  vector<int> log_;
  vector<vector<int>> father_;
  vector<vector<int>> min_;

  void DfsEuler(int vertex) {
    euler_path_.push_back(vertex);
    first_apparition_[vertex] = euler_path_.size() - 1;

    for (auto son : neighbors_[vertex]) {
      if (first_apparition_[son.first] == -1) {
        level_[son.first] = level_[vertex] + 1;
        father_[0][son.first] = vertex;
        min_[0][son.first] = son.second;
        DfsEuler(son.first);
        euler_path_.push_back(vertex);
      }
    }
  }

  void PrecalculateAncestors() {
    for (int i = 1; i < log_[num_vertices_]; i++) {
      for (int j = 1; j <= num_vertices_; j++) {
        father_[i][j] = father_[i - 1][father_[i - 1][j]];
        min_[i][j] = min(min_[i - 1][j], min_[i - 1][father_[i - 1][j]]);
      }
    }
  }

  int GetMinWithLCA(int x, int lca) {
    int how_much_up = level_[x] - level_[lca];
    int best = 1 << 30;
    for (int i = 0; (1 << i) <= how_much_up; i++) {
      if ((1 << i) & how_much_up) {
        best = min(best, min_[i][x]);
        x = father_[i][x];
      }
    }
    return best;
  }
};

int main() {
  cin.sync_with_stdio(false);

  ifstream cin("atac.in");
  ofstream cout("atac.out");

  int n, m, p;
  cin >> n >> m >> p;

  Tree tree(n, 1);
  for (int i = 2; i <= n; i++) {
    int x, z;
    cin >> x >> z;
    tree.AddEdge(i, x, z);
  }

  tree.Precalculate();

  int X, Y, A, B, C, D;
  cin >> X >> Y >> A >> B >> C >> D;

  for (int i = 1; i <= m; i++) {
    int Z = tree.GetMin(X, Y);
    if (i >= m - p + 1) {
      cout << Z << '\n';
    }

    X = (X * A + Y * B) % n + 1;
    Y = (Y * C + Z * D) % n + 1;
  }

  return 0;
}