Cod sursa(job #610880)

Utilizator danalex97Dan H Alexandru danalex97 Data 29 august 2011 15:43:43
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 32005
#define LOG 20

int str[LOG][DIM],min_c[LOG][DIM];
int n,m,p,x,y,z,a,b,c,d;
int dst[DIM];

void read ()
{
    int i;

    scanf ("%d%d%d",&n,&m,&p);
    for (i=2; i<=n; ++i)
        scanf ("%d%d",&str[0][i],&min_c[0][i]);
    scanf ("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
}

void df (int nod)
{
    if (!dst[str[0][nod]])
        df (str[0][nod]);
    dst[nod]=dst[str[0][nod]]+1;
}

void proc ()
{
    int i,j;

    dst[1]=1;
    for (i=1; i<=n; ++i)
        if (!dst[i])
            df (i);
    for (i=1; i<LOG; ++i)
        for (j=1; j<=n; ++j)
            if (dst[j]>(1<<i))
            {
                str[i][j]=str[i-1][str[i-1][j]];
                min_c[i][j]=min (min_c[i-1][j],min_c[i-1][str[i-1][j]]);
            }
}

inline int query (int x,int y)
{
    int i,min_val;

    if (x==y)
        return INF;
	if (dst[x]==dst[y])
	{
		min_val=min (min_c[0][x],min_c[0][y]);
        for (i=1; i<LOG && str[i][x]!=str[i][y]; ++i)
		{
			min_val=min (min_val,min_c[i][x]);
			min_val=min (min_val,min_c[i][y]);
		}
		return min (min_val,query (str[i-1][x],str[i-1][y]));
	}
	if (dst[x]<dst[y])
        swap (x,y);
	for (i=0; dst[y]+(1<<i)<=dst[x]; ++i);
	return min (min_c[i-1][x],query (str[i-1][x],y));
}

void solve ()
{
    int i;

    for (i=1; i<=m; ++i)
    {
        z=query (x,y);
        if (x==y)
            z=0;
		x=(x*a+y*b)%n+1;
		y=(y*c+z*d)%n+1;
        if (i>=m-p+1)
			printf ("%d\n",z);
	}
}

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

    read ();
    proc ();
    solve ();

    return 0;
}