Cod sursa(job #389171)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 1 februarie 2010 10:58:19
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<cstdio>
#include<vector>
#define N 32005
#define M 500001
#define minn(a,b) ((a<b)?(a):(b))
using namespace std;
vector<short int> gr(N);
vector<int> c(N),dist(N,0);
short int n,y;
int m,p,rez,x1,y1,a,b,c1,d,z;
/*short int find(short int x)
{
	if(gr[x]==x)
		return x;
	return find(gr[x]);
}*/
void df(short int x)
{
	if (gr[x]==x)
	{
		dist[x]=1;
		return;
	}
	df(gr[x]);
	dist[x]=1+dist[gr[x]];
}
void solve(int x1,int y1)
{
	rez=M;
	if (dist[x1]<dist[y1])
		swap(x1,y1);
	for (;dist[x1]>dist[y1];rez=minn(rez,c[x1]),x1=gr[x1]);
	while (x1!=y1)
	{	
		rez=minn(rez,minn(c[x1],c[y1]));
		x1=gr[x1];
		y1=gr[y1];
	}
}
void citire()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	scanf("%hd%d%d",&n,&m,&p);
	gr[1]=1;
	for(short int i=2; i<=n; ++i)
	{
		scanf("%hd%d",&y,&z);
		gr[i]=y;
		c[i]=z;
	}
	for (int i=1; i<=n; ++i)
		if (!dist[i])
			df(i);
	scanf("%d%d%d%d%d%d",&x1,&y1,&a,&b,&c1,&d);
	solve(x1,y1);
	for (int i=0; i<=m; ++i)
	{
		if (m-p+1<=i)
			printf("%d\n",rez);
		x1=(x1*a+y1*b)%n+1;
		y1=(y1*c1+rez*d)%n+1;
		solve(x1,y1);
	}
}
int main()
{
	citire();
	return 0;
}