Cod sursa(job #2756744)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 2 iunie 2021 19:18:35
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <algorithm>
#include <iostream>
#include <fstream>

std::fstream in("atac.in", std::ios::in);
std::fstream out("atac.out", std::ios::out);

const int nmax = 32e3;
const int INF = 2e9;

struct Edge {
    int x, y, cost;
    bool operator < (const Edge &other) const {
      return other.cost < cost;
    }
};

int lca(int x, int y, int minn);

void init();

void next(int a, int b, int c, int d, int zz, int p1, int p2, int minn, int &x, int &y);

int n, m, k;
int cost[1 + nmax];
int dad[1 + nmax];
int level[1 + nmax];

Edge g[1 + nmax];

int daddy(int el) {
  while(el != dad[el])
    el = dad[el];
  return el;
}

int papi(int el) {
  if(el == dad[el])
    return 0;
  papi(dad[el]);
  level[el] = level[dad[el]] + 1;
}

int main() {
  in >> n >> m >> k;
  for(int i = 1; i < n; ++ i) {
    g[i].x = i + 1;
    in >> g[i].y >> g[i].cost;
  }
  init();
  for(int i = 1; i <= n; ++ i) {
    if(level[i] == 0)
      papi(i);
  }
  int x, y, a, b, c, d;
  in >> x >> y >> a >> b >> c >> d;
  for(int i = 1; i <= m; i++) {
    int p1 = x;
    int p2 = y;
    int minn = INF;
    minn = lca(x, y, minn);
    next(a, b, c, d, i, p1, p2, minn, x, y);
  }
}

void next(int a, int b, int c, int d, int zz, int p1, int p2, int minn, int &x, int &y) {
  if(minn == INF)
    minn = 0;
  if(m - zz + 1 <= k)
    out << minn << '\n';
  x = (p1 * a + p2 * b) % n + 1;
  y = (p2 * c + minn * d) % n + 1;
}

void init() {
  for(int i = 1; i <= n; ++ i)
    dad[i] = i;
  std::sort(g + 1, g + n);
  for(int i = 1; i < n; ++ i) {
    int p1 = daddy(g[i].x);
    int p2 = daddy(g[i].y);
    if(p1 != p2) {
      dad[p1] = p2;
      cost[p1] = g[i].cost;
    }
  }
}

int lca(int x, int y, int minn) {
  while(level[x] > level[y]) {
    minn = std::min(minn, cost[x]);
    x = dad[x];
  }

  while(level[y] > level[x]) {
    minn = std::min(minn, cost[y]);
    y = dad[y];
  }

  while(x != y) {
    minn = std::min(minn, std::min(cost[x], cost[y]));
    x = dad[x];
    y = dad[y];
  }
  return minn;
}