Cod sursa(job #1794754)

Utilizator stoianmihailStoian Mihail stoianmihail Data 1 noiembrie 2016 18:22:44
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <stdio.h>
#include <limits.h>

#define MAX_N 32000
#define MAX_LOG 14

int N, M, P;
char lg[MAX_N + 1];
short int d[MAX_N + 1];
short int father[MAX_LOG + 1][MAX_N + 1];
int cost[MAX_LOG + 1][MAX_N + 1];

int MIN(int X, int Y) {
  return X < Y ? X : Y;
}

int depth(int u) {
  if (d[u] == 0) {
    d[u] = depth(father[0][u]) + 1;
  }
  return d[u];
}

int climb(int *u, int level) {
  int min = INT_MAX;

  while (level) {
    min = MIN(min, cost[lg[level & -level]][*u]);
    *u = father[lg[level & -level]][*u];
    level &= (level - 1);
  }
  return min;
}

int main(void) {
  int i, k, u, v, X, Y, Z, A, B, C, D;
  FILE *f = fopen("atac.in", "r");

  fscanf(f, "%d %d %d", &N, &M, &P);
  for (i = 2; i <= N; i++) {
    fscanf(f, "%hd %d", &father[0][i], &cost[0][i]);
    lg[i] = lg[i >> 1] + 1;
  }
  fscanf(f, "%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
  fclose(f);

  father[0][1] = 1;
  for (k = 1; k <= MAX_LOG; k++) {
    for (u = 1; u <= N; u++) {
      father[k][u] = father[k - 1][father[k - 1][u]];
      cost[k][u] = MIN(cost[k - 1][u], cost[k - 1][father[k - 1][u]]);
    }
  }

  d[1] = 1;
  for (u = 2; u <= N; u++) {
    depth(u);
  }

  freopen("atac.out", "w", stdout);
  while (M) {
    if (X != Y) {
      u = X;
      v = Y;
      if (d[u] > d[v]) {
        Z = climb(&u, d[u] - d[v]);
      } else {
        Z = climb(&v, d[v] - d[u]);
      }
      if (u != v) {
        for (k = lg[d[u]]; k >= 0; k--) {
          if (father[k][u] != father[k][v]) {
            Z = MIN(Z, MIN(cost[k][u], cost[k][v]));
            u = father[k][u];
            v = father[k][v];
          }
        }
        Z = MIN(Z, MIN(cost[0][u], cost[0][v]));
      }
    } else {
      Z = 0;
    }

    if (M <= P) {
      fprintf(stdout, "%d\n", Z);
    }
    //fprintf(stderr, "%d %d - %d\n", X, Y, Z);
    X = (X * A + Y * B) % N + 1;
    Y = (Y * C + Z * D) % N + 1;
    M--;
  }
  fclose(stdout);
  return 0;
}