Cod sursa(job #2194495)

Utilizator GoogalAbabei Daniel Googal Data 13 aprilie 2018 16:48:07
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <algorithm>
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 32 * 1e3;
const int INF = 1 << 30;

struct Edge {
  int x;
  int y;
  int cost;

  bool operator< (Edge other) const {
    return other.cost < cost;
  }
};

int n, m, k;
int cost[1 + NMAX];
int sef[1 + NMAX];
int level[1 + NMAX];

Edge g[1 + NMAX];

int get_sef(int el) {
  while(el != sef[el])
    el = sef[el];
  return el;
}

int get_level(int el) {
  if(el == sef[el])
    return 0;
  get_level(sef[el]);
  level[el] = level[sef[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;
  }

  for(int i = 1; i <= n; i++)
    sef[i] = i;
  sort(g + 1, g + n);

  for(int i = 1; i < n; i++) {
    int p1 = get_sef(g[i].x);
    int p2 = get_sef(g[i].y);

    if(p1 != p2) {
      sef[p1] = p2;
      cost[p1] = g[i].cost;
    }
  }

  for(int i = 1; i <= n; i++) {
    if(level[i] == 0)
      get_level(i);
  }

  int x, y, a, b, c, d;
  in >> x >> y >> a >> b >> c >> d;

  for(int zz = 1; zz <= m; zz++) {
    int p1 = x;
    int p2 = y;

    int minn = INF;
    while(level[x] > level[y]) {
      minn = min(minn, cost[x]);
      x = sef[x];
    }

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

    while(x != y) {
      minn = min(minn, min(cost[x], cost[y]));
      x = sef[x];
      y = sef[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;
  }

  in.close();
  out.close();
  return 0;
}