Cod sursa(job #2476859)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 19 octombrie 2019 11:56:19
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda teme_upb Marime 2.16 kb
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << x << endl

using namespace std;

void DFS(int node, const vector<vector<pair<int, int>>> &adj,
  vector<vector<int>> &rmq, vector<vector<int>> &anc, vector<int> &lvl) {
  for (int bit = 1; bit < (int)rmq[node].size(); ++bit) {
    if (anc[node][bit - 1] == -1) break; 
    anc[node][bit] = anc[anc[node][bit - 1]][bit - 1];
    rmq[node][bit] = min(rmq[node][bit - 1], rmq[anc[node][bit - 1]][bit - 1]);
  }
  for (auto &e : adj[node]) {
    int x, cost; tie(x, cost) = e;
    anc[x][0] = node;
    rmq[x][0] = cost;
    lvl[x] = lvl[node] + 1;
    DFS(x, adj, rmq, anc, lvl);
  }
}

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

  int n, m, p; cin >> n >> m >> p;
  vector<vector<pair<int, int>>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    int dad, val; cin >> dad >> val; --dad;
    adj[dad].emplace_back(i + 1, dad);
  }
  int logn = 32 - __builtin_clz(n);
  vector<vector<int>> rmq(n, vector<int>(logn)), anc(n, vector<int>(logn, -1));
  vector<int> lvl(n);
  DFS(0, adj, rmq, anc, lvl);
  int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;
  --x, --y;
  auto Query = [&](int x, int y) {
    int ans = (int)1e9 + 6;
    if (lvl[x] > lvl[y]) swap(x, y);
    int dist = lvl[y] - lvl[x];
    for (int bit = 0; dist != 0; ++bit) {
      if (dist & (1 << bit)) {
        ans = min(ans, rmq[y][bit]);
        y = anc[y][bit];
        dist ^= 1 << bit;
      }
    }
    if (x == y) return ans;
    for (int bit = logn - 1; bit >= 0; --bit) {
      if (anc[x][bit] == anc[y][bit]) continue;
      ans = min({ans, rmq[x][bit], rmq[y][bit]});
      x = anc[x][bit];
      y = anc[y][bit];
    }
    assert(anc[x][0] == anc[y][0]);
    ans = min({ans, rmq[x][0], rmq[y][0]});   
    return ans;
  };
  for (int i = 0; i < m; ++i) {
    int ans = Query(x, y);
    if (i >= m - p) cout << ans << '\n';
    x = (x * a + y * b) % n;
    y = (y * c + ans * d) % n;
  }
  for (int i = 0; i < n; ++i) {
    for (int bit = 0; anc[i][bit] != -1; ++bit) {
      cerr << "nod: " << i << " dist " << (1 << bit) << ' ' << rmq[i][bit] << endl;
    }
  }
}