Cod sursa(job #1246202)

Utilizator hrazvanHarsan Razvan hrazvan Data 20 octombrie 2014 19:19:42
Problema Atac Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 3.56 kb
#include <stdio.h>
#define INF 2000000000
#define MAXN 32000
#define MAXLG 16

typedef struct{
  int nod, next, cost;
}graf;

graf adj[2 * MAXN];
int ult[MAXN + 1];
int eunod[2 * MAXN], euad[2 * MAXN - 1], apar[MAXN + 1];
int rmq[MAXLG + 1][2 * MAXN];
int tati[MAXLG + 1][MAXN + 1], stram[MAXLG + 1][MAXN + 1], adanc[MAXN + 1];
char trecut[MAXN + 1];
char lg[2 * MAXN];

inline int max2(int a, int b){
  return a > b ? a : b;
}

inline int min2(int a, int b){
  return a < b ? a : b;
}

inline void add(int x, int y, int cost, int *k){
  adj[*k].nod = y;
  adj[*k].next = ult[x];
  adj[*k].cost = cost;
  ult[x] = *k;
  (*k)++;
}

void eu(int x, int *k, int ad){
  trecut[x] = 1;
  if(apar[x] == 0)  apar[x] = *k;
  eunod[*k] = x;
  euad[*k] = ad;
  (*k)++;
  int poz = ult[x];
  while(poz > 0){
    if(!trecut[adj[poz].nod]){
      eu(adj[poz].nod, k, ad + 1);
      eunod[*k] = x;
      euad[*k] = ad;
      (*k)++;
    }
    poz = adj[poz].next;
  }
}

inline void aflu(int n, int k){
  int i, j, poz = 2 * n - 1, ind = 1;
  for(i = 1; i <= n; i++)  trecut[i] = 0;
  eu(1, &ind, 1);
  for(i = 1; i <= poz; i++)  rmq[0][i] = i;
  for(i = 1; i <= MAXLG; i++){
    for(j = 1; j <= poz; j++){
      rmq[i][j] = euad[rmq[i - 1][j]] < euad[rmq[i - 1][max2(1, j - (1 << (i - 1)))]] ?
                  rmq[i - 1][j] : rmq[i - 1][max2(1, j - (1 << (i - 1)))];
    }
  }
}

inline void loga(){
  int i = 0, k = 0, pt = 1;
  for(i = 2; i < (MAXN << 1) - 1; i++){
    lg[i] = k;
    if(i == 1 << pt){
      k++;
      pt++;
    }
  }
}

inline void afltati(int x, int n){
  int i, st = 0, dr = 1, poz, qu[MAXN];
  for(i = 0; i <= n; i++)  trecut[i] = 0;
  adanc[x] = 1;
  qu[0] = x;
  trecut[x] = 1;
  while(st < dr){
    poz = ult[qu[st]];
    while(poz > 0){
      if(!trecut[adj[poz].nod]){
        adanc[adj[poz].nod] = adanc[qu[st]] + 1;
        qu[dr] = adj[poz].nod;
        dr++;
        trecut[adj[poz].nod] = 1;
        tati[0][adj[poz].nod] = qu[st];
        stram[0][adj[poz].nod] = adj[poz].cost;
      }
      poz = adj[poz].next;
    }
    st++;
  }
  int j;
  for(i = 1; i <= MAXLG; i++){
    for(j = 1; j <= n; j++){
      tati[i][j] = tati[i - 1][tati[i - 1][j]];
      stram[i][j] = min2(stram[i - 1][j], stram[i - 1][tati[i - 1][j]]);
    }
  }
}

inline int minim(int x, int poz){
  int rez = INF, pas = MAXLG;
  while(pas >= 0){
    if(adanc[tati[pas][x]] >= adanc[poz]){
      rez = min2(rez, stram[pas][x]);
      x = tati[pas][x];
    }
    pas--;
  }
  return rez;
}

inline int boom(int x, int y){
  int poz1 = apar[x], poz2 = apar[y], aux;
  if(poz1 > poz2){
    aux = poz1;  poz1 = poz2;  poz2 = aux;
  }
  int logr = lg[poz2 - poz1 + 1], poz;
  poz = euad[rmq[logr][poz2]] < euad[rmq[logr][poz1 + (1 << logr) - 1]] ?
          rmq[logr][poz2] : rmq[logr][poz1 + (1 << logr) - 1];
  return min2(minim(x, eunod[poz]), minim(y, eunod[poz]));
}

int main(){
  FILE *in = fopen("atac.in", "r");
  int n, m, p, i, u, v, k = 1;
  fscanf(in, "%d%d%d", &n, &m, &p);
  for(i = 2; i <= n; i++){
    fscanf(in, "%d%d", &u, &v);
    add(i, u, v, &k);
    add(u, i, v, &k);
  }
  aflu(n, k);
  loga();
  afltati(1, n);
  int x, y, a, b, c, d, aux, bm;
  fscanf(in, "%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
  fclose(in);
  FILE *out = fopen("atac.out", "w");
  for(i = 1; i <= m; i++){
    aux = x;
    bm = boom(x, y);
    x = (aux * a + y * b) % n + 1;
    y = (y * c + bm * d) % n + 1;
    if(i >= m - p + 1){
      fprintf(out, "%d\n", bm);
    }
  }
  fclose(out);
  return 0;
}