Cod sursa(job #2890211)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 14 aprilie 2022 22:14:03
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int LOG2MAX = 14;
const int NMAX = 32000;
const int INF = 1e9;

int n, m, p;
int punctaj[NMAX + 5];
vector<pair<int, int>> v[NMAX + 5];
bool are_tata[NMAX + 5];

int parcurgere_euler[2 * NMAX + 5], vf_parcurgere_euler;
int first_ap[NMAX + 5];
int h[2 * NMAX + 5];
int log2[2 * NMAX + 5];
int rmq[LOG2MAX + 5][2 * NMAX + 5];
int rmq_bombe[LOG2MAX + 5][NMAX + 5];
int stramosi[LOG2MAX + 5][NMAX + 5];

void dfs(int nod, int dad) {
  parcurgere_euler[++vf_parcurgere_euler] = nod;
  first_ap[nod] = vf_parcurgere_euler;

  for(pair<int, int> mch: v[nod]) {
    int fiu = mch.first, cost = mch.second;
    if(fiu == dad)
      continue;

    h[fiu] = h[nod] + 1;
    rmq_bombe[0][fiu] = cost;
    stramosi[0][fiu] = nod;
    for(int i = 1, p2 = 2; p2 < h[fiu]; i++, p2 <<= 1) {
      stramosi[i][fiu] = stramosi[i - 1][ stramosi[i - 1][fiu] ];
      rmq_bombe[i][fiu] = min(rmq_bombe[i - 1][fiu], rmq_bombe[i - 1][ stramosi[i - 1][fiu] ]);
    }

    dfs(fiu, nod);
    parcurgere_euler[++vf_parcurgere_euler] = nod;
  }
}

void calc_log2() {
  log2[1] = 0;
  for(int i = 2; i <= vf_parcurgere_euler; i++)
    log2[i] = log2[i / 2] + 1;
}

void calc_rmq() {
  for(int i = 1; i <= vf_parcurgere_euler; i++)
    rmq[0][i] = parcurgere_euler[i];

  for(int i = 1, p2 = 2; i <= log2[vf_parcurgere_euler]; i++, p2 <<= 1)
    for(int j = 1; j + p2 - 1 <= vf_parcurgere_euler; j++) {
      int nod_st = rmq[i - 1][j];
      int nod_dr = rmq[i - 1][j + p2 / 2];
      rmq[i][j] = (h[nod_st] <= h[nod_dr] ? nod_st : nod_dr);
    }
}

int lca(int a, int b) {
  if(first_ap[a] > first_ap[b])
    swap(a, b);

  int l = first_ap[b] - first_ap[a] + 1;
  int nod_st = rmq[ log2[l] ][ first_ap[a] ];
  int nod_dr = rmq[ log2[l] ][ first_ap[b] - (1 << log2[l]) + 1 ];
  return (h[nod_st] <= h[nod_dr] ? nod_st : nod_dr);
}

// intoarce valoarea minima a unei muchii de pa lantul de la fiu la tata
int min_lant(int tata, int fiu) {
  int nr_muchii = h[fiu] - h[tata];
  int ret = INF;

  for(int i = 0, p2 = 1; p2 <= nr_muchii; i++, p2 <<= 1)
    if(nr_muchii & p2) {
      ret = min(ret, rmq_bombe[i][fiu]);
      fiu = stramosi[i][fiu];
    }

  return ret;
}

int main() {
  freopen("atac.in", "r", stdin);
  freopen("atac.out", "w", stdout);

  scanf("%d %d %d", &n, &m, &p);
  for(int i = 2; i <= n; i++) {
    int U, V;
    scanf("%d %d", &U, &V);
    v[U].push_back({i, V});
    v[i].push_back({U, V});
  }

  h[1] = 1;
  dfs(1, 0);
  calc_log2();
  calc_rmq();

  int x, y, z = 0, a, b, c, d;
  scanf("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d);
  for(int i = 1; i <= m; i++) {
    if(x != y) {
      int lca_xy = lca(x, y);
      z = min(min_lant(lca_xy, x), min_lant(lca_xy, y));
    }
    else
      z = 0;

    if(i > m - p)
      printf("%d\n", z);

    int new_x = (x * a + y * b) % n + 1;
    int new_y = (y * c + z * d) % n + 1;
    x = new_x, y = new_y;
  }

  return 0;
}