Cod sursa(job #2756799)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 2 iunie 2021 22:33:12
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

const int MAXN = 1 << 15;
vector<pair<int,int>> G[MAXN];
int lg2[MAXN], depth[MAXN];

struct lca_node {
  int prv, mn;
} ancestor[MAXN][15];

void dfs(int u, int parent, int edge_wt) {
  ancestor[u][0] = lca_node{parent, edge_wt};
  for (int lift = 1; lift < 15; ++lift) {
    lca_node &p = ancestor[u][lift];
    lca_node half_ancestor = ancestor[u][lift - 1];
    p.prv = ancestor[half_ancestor.prv][lift - 1].prv;
    p.mn = min(half_ancestor.mn, ancestor[half_ancestor.prv][lift - 1].mn);
  }
  for (auto it : G[u]) {
    int v, w;
    tie(v, w) = it;
    if (v != parent) {
      depth[v] = depth[u] + 1;
      dfs(v, u, w);
    }
  }
}

void min_self(int &x, int y) {
  x = min(x, y);
}

int query_min(int u, int v) {
  if (depth[u] < depth[v])
    swap(u, v);
  int ans = INF;
  for (int lift = lg2[depth[u]]; lift >= 0; --lift)
    if (depth[u] - (1 << lift) >= depth[v]) {
      lca_node node = ancestor[u][lift];
      min_self(ans, node.mn);
      u = node.prv;
    }
  if (u == v)
    return ans;
  for (int lift = lg2[depth[u]]; lift >= 0; --lift) {
    lca_node x = ancestor[u][lift], y = ancestor[v][lift];
    if (x.prv != y.prv) {
      min_self(ans, x.mn);
      min_self(ans, y.mn);
      u = x.prv;
      v = y.prv;
    }
  }
  return min({ans, ancestor[u][0].mn, ancestor[v][0].mn});
}

int main() {
  int n, m, p;
  fin >> n >> m >> p;
  for (int v = 2; v <= n; ++v) {
    int u, w;
    fin >> u >> w;
    G[u].emplace_back(v, w);
    lg2[v] = lg2[v >> 1] + 1;
  }
  dfs(1, 0, INF);
  int X, Y, A, B, C, D;
  fin >> X >> Y >> A >> B >> C >> D;
  for (int i = 0; i < m; ++i) {
    int Z = query_min(X, Y);
    X = (X * A + Y * B) % n + 1;
    Y = (Y * C + Z * D) % n + 1;
    if (m - i <= p)
      fout << Z << '\n';
  }
  fin.close();
  fout.close();
  return 0;
}