Cod sursa(job #10940)

Utilizator mockeBarca Cristian Mihai mocke Data 29 ianuarie 2007 23:16:23
Problema Atac Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#define PB push_back
#define MAX(a, b) ( (a) < (b) ? (b) : (a) )
#define MIN(a, b) ( (a) > (b) ? (b) : (a) )
#define INF 1000000001
#define NMAX 32012
#define LGNMAX 16

using namespace std;

vector <int> A[NMAX], C[NMAX];

int T[LGNMAX][NMAX], Dmin[LGNMAX][NMAX];
int used[NMAX], St[NMAX];
int in[NMAX], out[NMAX];
int i, j, k, N, M, logN, K, P;
int x, y, z, a, b, c, d, nod, cost;

void prep()
{
	in[0] = -INF;
	out[0] = +INF;

     for (k = 1; k <= logN; k++)
         for (i = 1; i <= N; i++)
             if (used[i] == 1)
             {
                    T[k][i] = T[k-1][ T[k-1][i] ];

                    Dmin[k][i] = MIN( Dmin[k-1][i], Dmin[k-1][ T[k-1][i] ] );
             }
}

void DF(int source)
{
     int elem, i, Tt = 0;

     St[0] = source;

     St[++k] = source;
     used[source] = 1;
     Dmin[0][source] = +INF;
     in[source] = ++Tt;

     while (k > 0)
     {
          elem = -1;
		  
		  int sz = A[St[k]].size();

          for  (i = 0; i < sz; i++)
               if ( !used[ A[St[k]][i] ] )
               {
                    elem = A[St[k]][i];
                    break;
               }

          if (elem > -1 && !used[elem])
          {
               Dmin[0][elem] = C[St[k]][i];
               St[++k] = elem;
               used[elem] = 1;
               in[elem] = ++Tt;
          }
          else
          {
               T[0][St[k]] = St[k-1];
               out[St[k]] = ++Tt;
               St[k--] = 0;
          }
     }
}

inline int e_stramos(int i, int j)
{
     return (in[i] <= in[j] && out[j] <= out[i]);
}

int calc_dist(int x, int y)
{
     int k, stramos = x, dist = +INF, xp = x;
	 
     if (e_stramos(x, y)) return +INF;

     for (k = logN; k >= 0; k--)
         if (e_stramos(T[k][xp], y))
         {
               stramos = T[k][xp];
         }
         else
         {
               dist = MIN(dist, Dmin[k][xp]);
               xp = T[k][xp];
         }

     if (stramos != x)
         return MIN(dist, Dmin[0][xp]);

     return +INF;
}

int main()
{
	freopen("atac.in", "r",  stdin);
	freopen("atac.out", "w", stdout);

	scanf("%d %d %d", &N, &M, &P);

	logN = 0;

	while ( (1<<logN) < N) logN ++;
	
	for (i = 1; i <= N; i++) A[i].reserve(3), C[i].reserve(3);
	
	for (i = 2; i <= N; i++)
	{
			scanf("%d %d", &nod, &cost);
				
			A[i].PB(nod);
			A[nod].PB(i);
			C[i].PB(cost);
			C[nod].PB(cost);
	}
		
	DF(1);

	prep();
	
	scanf("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d);
	
	for (i = 1; i <= M; i++)
    {
          if (x != y)
		  {
		
			  int s1 = calc_dist(x, y);
			  int s2 = calc_dist(y, x);

			  z = MIN(s1, s2);
		  }
		  else z = 0;
		  
		  if (i >= M - P + 1) printf("%d\n", z);
			  
		  x = ((x * a + y * b) % N) + 1;
		  y = ((y * c + z * d) % N) + 1;
     }

	 
	 fclose(stdin);
     fclose(stdout);

     return 0;

}