Cod sursa(job #520263)

Utilizator bora_marianBora marian bora_marian Data 7 ianuarie 2011 19:16:36
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include<fstream>
using namespace std;
int stra[20][32003],rq[20][32003];
int n,a,b,c,d,m,p,x,y,nr,nivel[32003],t[32003],z;
struct nod{
	int info;
	int bomb;
	nod *next;};
nod *g[32003];
int maxim;
void citire();
void creeaza();
void dfs(int k);
int raspunde(int x,int y);
void adauga(int a,int b,int bombe);
int min(int a,int b)
{
	if(a<b)
	 return a;
	else
	 return b;
 } 
int main()
{
	ofstream fout("atac.out");
	citire();
	dfs(1);
	creeaza();
	int i;
	for(i=1;i<=m;i++)
	{
		if(x==y)
		  z=0;
		else
		  z=raspunde(x,y);
		if(i>=m-p+1)
		   fout<<z<<"\n";
		x=(x*a+y*b)%n+1;
		y=(y*c+z*d)%n+1;
       	
     }
     return 0;
} 

void citire()
{
	ifstream fin("atac.in");
	fin>>n>>m>>p;
	int i;
	for(i=2;i<=n;i++)
	{
		int nodu,bombe;
		fin>>nodu>>bombe;
		if(bombe>maxim)
		   maxim=bombe;
		adauga(i,nodu,bombe);
		adauga(nodu,i,bombe);
		t[i]=-1;
	}
	fin>>x>>y>>a>>b>>c>>d;
    t[1]=0;
    nivel[1]=1;
    rq[0][1]=maxim+1;  
}
void dfs(int k)
{
	for(nod *p=g[k];p;p=p->next)
	{
		if(t[p->info]==-1)
		{
		   t[p->info]=k;
		   rq[0][p->info]=p->bomb;
		   nivel[p->info]=nivel[k]+1;
		   dfs(p->info);
	    }
	}
}
void creeaza()
{
	int i,j;
	for(i=1;i<=n;i++)
	   stra[0][i]=t[i];
	int pres=1;
	for(i=1;pres==1;i++)
	{
		pres=0;
		for(j=1;j<=n;j++)
		{
			stra[i][j]=stra[i-1][stra[i-1][j]];
			rq[i][j]=min(rq[i-1][j],rq[i-1][stra[i-1][j]]);
			if(stra[i][j]>0)
			   pres=1;
		 }
	 }		   
}
int raspunde(int x,int y)
{
	int sol=min(rq[0][x],rq[0][y]);
	int mic,mare;
	if(nivel[x]>nivel[y])
	   mare=x,mic=y;
	else
	   mare=y,mic=x;
	int i=0;
	while(nivel[stra[i+1][mare]]>=nivel[mic])
	{
		i++;
		if(rq[i][mare]<sol && rq[i][mare]>0)
		  sol=rq[i][mic];
	}
	mare=stra[i][mare];
    while(nivel[t[mare]]>=nivel[mic])
	{   
	   if(rq[0][mare]<sol && rq[0][mare]>0)
	     sol=rq[0][mare];
	   mare=t[mare];  
	 } 
	i=0;
	int pres=0;
	while(pres==0)
	{
		if(stra[i+1][mare]!=stra[i+1][mic])
		     i++;
		else
		    pres=1;
		if(rq[i][mare]<sol && rq[i][mare]>0)
		   sol=rq[i][mare];
		if(rq[i][mic]<sol && rq[i][mic]>0)
		   sol=rq[i][mic];
	}
	mare=stra[i][mare],mic=stra[i][mic];
	pres=0;
	if(mare!=mic)
	{
	   while(pres==0)
	   {
		   if(rq[0][mare]<sol && rq[0][mare]>0)
		      sol=rq[0][mare];
		   if(rq[0][mic]<sol && rq[0][mic]>0)
		      sol=rq[0][mic];
		   if(mare==mic)
		      pres=1;
		   mare=t[mare];
		   mic=t[mic];   
		  }
	  }
	return sol;
}
void adauga(int a,int b,int bombe)
{
	nod *p=new nod;
	p->info=b;
	p->bomb=bombe;
	p->next=g[a];
	g[a]=p;
}