Cod sursa(job #1536013)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 25 noiembrie 2015 15:58:52
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <stdio.h>

#define MAX_N 32000
#define MAX_LOG 15
#define NIL -1
#define INF 0x3F3F3F3F
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define LOG2(X) (31 - __builtin_clz((X)))

typedef struct {
  int v, next;
} cell;

cell l[MAX_N - 1];
int adj[MAX_N];
int anc[MAX_LOG][MAX_N];
int cost[MAX_LOG][MAX_N];
int depth[MAX_N];

void addEdge(int u, int v, int pos) {
  l[pos].v = v;
  l[pos].next = adj[u];
  adj[u] = pos;
}

void DFS(int u) {
  int i, v;
  for ( i = adj[u]; i != NIL; i = l[i].next ) {
    v = l[i].v;
    depth[v] = depth[u] + 1;
    DFS(v);
  }
}

int main(void) {
  FILE *fin, *fout;
  int n, q, k, i, j;
  int nQ;
  int u, v, a, b, c, d;
  int tmp;

  fin = fopen( "atac.in", "r" );
  fscanf( fin, "%d%d%d", &n, &q, &nQ );
  for ( i = 0; i < n; i++ ) {
    adj[i] = NIL;
  }
  for ( i = 1; i < n; i++ ) {
    fscanf( fin, "%d%d", &anc[0][i], &cost[0][i] );
    anc[0][i]--;
    addEdge( anc[0][i], i, i - 1 );
  }
  fscanf( fin, "%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d );
  fclose( fin );

  depth[0] = 1;
  DFS( 0 );

  for ( i = 1; (1 << i) <= n; i++ ) {
    for ( j = 0; j < n; j++ ) {
      cost[i][j] = MIN( cost[i][j], cost[i][ anc[i - 1][j] ] );
      anc[i][j] = anc[i - 1][ anc[i - 1][j] ];
    }
  }

  fout = fopen( "atac.out", "w" );
  while ( q-- ) {
    i = u; j = v;
    u--; v--;
    if ( depth[u] > depth[v] ) {
      tmp = u;
      u = v;
      v = tmp;
    }
    tmp = 0;
    if ( u != v ) {
      tmp = INF;
      for ( k = LOG2( depth[v] ); k >= 0; k-- ) {
        if ( depth[v] - (1 << k) >= depth[u] ) {
          tmp = MIN( tmp, cost[k][v] );
          v = anc[k][v];
        }
      }
      if ( u != v ) {
        for ( k = LOG2( depth[u] ); k >= 0; k-- ) {
          if ( anc[k][u] && anc[k][u] != anc[k][v] ) {
            tmp = MIN( cost[k][u], tmp );
            tmp = MIN( cost[k][v], tmp );
            u = anc[k][u]; v = anc[k][v];
          }
        }
        tmp = MIN( cost[0][u], tmp );
        tmp = MIN( cost[0][v], tmp );
      }
    }
    if ( q < nQ ) {
      fprintf( fout, "%d\n", tmp );
    }
    u = ( i * a + j * b ) % n + 1;
    v = ( j * c + tmp * d ) % n + 1;
  }
  fclose( fout );
  return 0;
}