Cod sursa(job #520286)

Utilizator bora_marianBora marian bora_marian Data 7 ianuarie 2011 20:57:46
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include<fstream>
using namespace std;
int t[20][32003],rq[20][32003];
int n,a,b,c,d,m,p,x,y,nr,nivel[32003],z;
struct nod{
	int info;
	int bomb;
	nod *next;};
nod *g[32003];
int maxim;
void citire();
void creeaza();
void dfs(int k);
int lca(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 dist(int x,int y);  
int main()
{
	ofstream fout("atac.out");
	citire();
	dfs(1);
	creeaza();
	int i;
	for(i=1;i<=m;i++)
	{
		if(x==y)
		  z=0;
		else
		 {
			 int stra=lca(x,y);
			 z=min(dist(x,stra),dist(y,stra));
		 }
		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[0][i]=-1;
	}
	fin>>x>>y>>a>>b>>c>>d;
    t[0][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[0][p->info]==-1)
		{
		   t[0][p->info]=k;
		   rq[0][p->info]=p->bomb;
		   nivel[p->info]=nivel[k]+1;
		   dfs(p->info);
	    }
	}
}
void creeaza()
{
	int i,j;
	int pres=1;
	for(i=1;pres==1;i++)
	{
		pres=0;
		for(j=1;j<=n;j++)
		{
			t[i][j]=t[i-1][t[i-1][j]];
			rq[i][j]=min(rq[i-1][j],rq[i-1][t[i-1][j]]);
			if(t[i][j]>0)
			   pres=1;
		 }
	 }		   
}
int lca(int x,int y)
{
  int aux;
  if(nivel[x]<nivel[y])
  {
	  aux=x;
	  x=y;
	  y=x;
  } 
  int log1=1,log2=1;
  for(;(1<<log1)<nivel[x];log1++);
  for(;(1<<log2)<nivel[y];log2++);
  
  for(int k=log1;k>0;k--)
      if(nivel[x]-(1>>k)>=nivel[y])
              x=t[k][x];
  if(x==y)
     return x;
  for(int k=log2;k>=0;k--)
     if(t[k][x]!=t[k][y])
     {
		 x=t[k][x];
		 y=t[k][y];
	 }
   return t[0][x];	                     	
}
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;
}
int dist(int x,int y)
{
	int sol=2147000000;	   
    int log1=1;
    for(;(1<<log1)<nivel[x];log1++)
    
    for(int k=log1;k>=0;k--)
       if(nivel[x]-(1>>k)>nivel[y])
       {
		   if(rq[k][x]<sol)
		      sol=rq[k][x];
		   x=t[k][x];
	   }
	return sol;
}