Cod sursa(job #389124)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 31 ianuarie 2010 23:18:06
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>
#include<vector>
#define N 32001
#define M 100001
#define minn(a,b) ((a<b)?(a):(b))
using namespace std;
vector<short int> y(N),gr(N);
vector<int> c(N),z(N),dist(N,0);
short int n;
int m,p,rez,x1,y1,a,b,c1,d;
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()
{
	rez=M;
	if (dist[x1]<dist[y1])
		swap(x1,y1);
	for (;dist[x1]>dist[y1];rez=minn(rez,c[x1]),x1=gr[x1]);
	for (;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);
	for(short int i=2; i<n; ++i)
		scanf("%hd%d",&y[i],&z[i]);
	for (int i=1; i<=n; ++i)
		gr[i]=i;
	short int u,v,i;
	for(short int j=1; j<n; ++j)
	{
		i=j+1;
		u=find(i);
		v=find(y[i]);
		gr[u]=v;
		c[u]=z[i];
	}
	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();
	for (int i=1; 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;
	}
}
int main()
{
	citire();
	return 0;
}