Cod sursa(job #2708877)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 19 februarie 2021 15:44:09
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb

#include <bits/stdc++.h>

using namespace std;

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

const int N = 32002;

int n, m, p, x, y, a, b, c, d, z;
int dp[20][N];
int par[20][N], lvl[N];
vector<pair<int, int> >G[N];

void dfs (int x, int p = 0, int len = 1e9) {
  par[0][x] = p;
  dp[0][x] = len;
  lvl[x] = lvl[p] + 1;
  for (auto it : G[x])
    if (it.first != p) {
      dfs(it.first, x, it.second);
    }
}

int query (int x, int y) {
  if (x == y)
    return 0;
  if (lvl[x] < lvl[y])
    swap(x, y);
  int ans = 1e9;
  int d = lvl[x] - lvl[y];
  for (int i = 19; i >= 0; i--)
    if (d & (1 << i)) {
      ans  = min(ans, dp[i][x]);
      x = par[i][x];
    }
  if (x == y)
    return ans;
  for (int i = 19; i >= 0; i--)
    if (par[i][x] != par[i][y]) {
      ans = min(ans, min(dp[i][x], dp[i][y]));
      x = par[i][x];
      y = par[i][y];
    }
  ans = min(ans, dp[0][x]);
  ans = min(ans, dp[0][y]);
  return ans;
}

int main()
{
  fin >> n >> m >> p;
  for (int i = 2; i <= n; i++) {
    int x, y;
    fin >> x >> y;
    G[i].push_back({x, y});
    G[x].push_back({i, y});
  }
  dfs(1);
  fin >> x >> y >> a >> b >> c >> d;
  for (int i = 1; (1 << i) <= n; i++)
    for (int j = 1; j <= n; j++) {
      par[i][j] = par[i - 1][par[i - 1][j]];
      dp[i][j] = min(dp[i - 1][j], dp[i - 1][par[i - 1][j]]);
    }
  for (int i = 1; i <= m; i++) {
    int ans = query(x, y);
    //cout << ans << "\n";
    x = (x * a + y * b) % n + 1;
    y = (y * c + ans * d) % n + 1;
    if (i >= m - p + 1)
      fout << ans << "\n";
  }
  return 0;
}