Cod sursa(job #2782795)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 13 octombrie 2021 08:20:18
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <vector>

using namespace std;

const int N = 32e3 + 5;
const int LOG = 16;
const int INF = (1 << 30);

struct edge {
  int to;
  int dist;
};

int up[N][LOG], mini[N][LOG], niv[N];
bool viz[N];

vector<edge> gr[N];
vector<int> ans;

void dfs(int nod) {
  viz[nod] = true;
  for (int i = 1; i < LOG; ++i)
    up[nod][i] = up[up[nod][i - 1]][i - 1];
  for (int i = 1; i < LOG; ++i)
    mini[nod][i] = min(mini[nod][i - 1], mini[up[nod][i - 1]][i - 1]);
  for (auto e : gr[nod])
    if (!viz[e.to]) {
      niv[e.to] = niv[nod] + 1;
      up[e.to][0] = nod;
      mini[e.to][0] = e.dist;
      dfs(e.to);
    }
}

int calc(int x, int y) {
  if (niv[x] < niv[y])
    swap(x, y);
  int dif = niv[x] - niv[y], rez = INF;
  for (int i = LOG - 1; i >= 0; --i)
    if (dif & (1 << i)) {
      rez = min(rez, mini[x][i]);
      x = up[x][i];
    }
  for (int i = LOG - 1; i >= 0; --i)
    if (up[x][i] != up[y][i]) {
      rez = min(rez, mini[x][i]);
      rez = min(rez, mini[y][i]);
      x = up[x][i];
      y = up[y][i];
    }
  rez = min(rez, mini[x][0]);
  rez = min(rez, mini[y][0]);
  return rez;
}

int main() {
  ifstream cin("atac.in");
  ofstream cout("atac.out");
  int n, m, p;
  cin >> n >> m >> p;
  for (int y = 2; y <= n; ++y) {
    int x, val;
    cin >> x >> val;
    gr[x].push_back({y, val});
    gr[y].push_back({x, val});
  }
  dfs(1);
  int x, y, a, b, c, d;
  cin >> x >> y >> a >> b >> c >> d;
  cin.close();
  for (int i = 0; i < m; ++i) {
    int z;
    if (x == y) z = 0;
    else z = calc(x, y);
    ans.push_back(z);
    x = ((long long) x * a + y * b) % n + 1;
    y = ((long long) y * c + z * d) % n + 1;
  }
  for (int i = ans.size() - p; i < ans.size(); ++i)
    cout << ans[i] << "\n";
  cout.close();
  return 0;
}