Cod sursa(job #2633937)

Utilizator lucametehauDart Monkey lucametehau Data 9 iulie 2020 11:39:36
Problema Atac Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("atac.in");
ofstream cout ("atac.out");

int n, m, p, x, y, a, b, c, d;

vector <pair <int, int>> g[32005];
int t[16][32005], mn[16][32005], h[32005];

void dfs(int nod) {
  for(auto &i : g[nod]) {
    int fiu = i.first, cost = i.second;
    if(!t[0][fiu]) {
      t[0][fiu] = nod;
      mn[0][fiu] = cost;
      h[fiu] = h[nod] + 1;
      dfs(fiu);
    }
  }
}

int tata(int nod, int x) {
  int p = 1, cnt = 0;
  while(x) {
    if(p & x)
      nod = t[cnt][nod], x ^= p;
    p <<= 1;
    cnt++;
  }
  return nod;
}

int lca(int x, int y) {
  int st = 0, dr = min(h[x], h[y]), mid;
  while(st <= dr) {
    mid = (st + dr) >> 1;
    if(tata(x, h[x] - mid) == tata(y, h[y] - mid))
      st = mid + 1;
    else
      dr = mid - 1;
  }
  return tata(x, h[x] - dr);
}

int getMin(int nod, int x) {
  int ans = 100005, p = 1, cnt = 0;
  while(x) {
    if(p & x) {
      ans = min(ans, mn[cnt][nod]);
      nod = t[cnt][nod];
      x ^= p;
    }
    p <<= 1;
    cnt++;
  }
  return ans;
}

int solve(int x, int y) {
  if(x == y)
    return 0;
  int nod = lca(x, y);
  return min(getMin(x, h[x] - h[nod]), getMin(y, h[y] - h[nod]));
}

int main() {
  cin >> n >> m >> p;
  for(int i = 2; i <= n; i++) {
    cin >> x >> y;
    g[i].push_back({x, y});
    g[x].push_back({i, y});
  }
  dfs(1);
  for(int i = 1; i <= 15; i++) {
    for(int j = 1; j <= n; j++) {
      t[i][j] = t[i - 1][t[i - 1][j]];
      mn[i][j] = min(mn[i - 1][j], mn[i - 1][t[i - 1][j]]);
    }
  }
  cin >> x >> y >> a >> b >> c >> d;
  for(; m; m--) {
    int z = solve(x, y);
    if(m <= p)
      cout << z << "\n";
    x = (x * a + y * b) % n + 1;
    y = (y * c + z * d) % n + 1;
  }
  return 0;
}