Cod sursa(job #519762)

Utilizator bora_marianBora marian bora_marian Data 6 ianuarie 2011 14:24:15
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include<fstream>
#include<cmath>
using namespace std;
int euler[300000],rq[32004],nivel[32004],eulercost[300000],lun;
struct nod{
	int info;
	int bomb;
	nod *next;
	};
nod *g[32003];
int n,x,z,y,p,m,a,b,c,d,nreuler,vizitat[32000],aparitii[32000],maxim,t[32004],nr;
void citire();
void dfs(int k);
void adauga(int a,int b,int bombe);
void impartire();
int rmq(int poz1,int poz2);
int main()
{
	int i;
	ofstream fout("atac.out");
	citire();
	dfs(1);
	nr--;
	impartire();
	for(i=1;i<=m;i++)
	{
		if(aparitii[x]<aparitii[y])
		   z=rmq(aparitii[x],aparitii[y]);
		else
		   z=rmq(aparitii[y],aparitii[x]);
		if(m-i+1<=p)
		   fout<<z<<"\n";
		x=(x*a+y*b)%n+1;
		y=(y*c+z*d)%n+1;
	}         
}	
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);
	}
	fin>>x>>y>>a>>b>>c>>d;
	euler[++nr]=1;
	nivel[0]=1;
	eulercost[1]=maxim+1;
	aparitii[1]=1;
	
}
void dfs(int k)
{
	vizitat[k]=1;
	nivel[k]=nivel[t[k]]+1;
	for(nod *p=g[k];p;p=p->next)
	   if(vizitat[p->info]==0)
	   {   
	      euler[++nr]=p->info;
	      aparitii[p->info]=nr;
	      eulercost[nr]=p->bomb;
	      t[p->info]=k;
	      dfs(p->info);
	   }
	   euler[++nr]=t[k];
	   eulercost[nr]=maxim+1;
}
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;
}	   
void impartire()
{
	lun=sqrt(nr);
	int i;
	for(i=1;i<=nr;i++)	
    {    
        int parte=i/lun;
        if(i%lun>0)
           parte++;
         if(rq[parte]==0)
            rq[parte]=eulercost[i];
         else
            if(eulercost[i]<rq[parte])
               rq[parte]=eulercost[i];
	}
}
int rmq(int poz1,int poz2)
{
	int inceput=poz1/lun+1;
	int sf=poz2/lun;
	int minim=maxim+2;
	int i;
	for(i=poz1;i<=inceput*lun;i++)
	    if(eulercost[i]<minim) 
	       minim=eulercost[i];
	for(i=inceput;i<=sf;i++)
	    if(rq[i]<minim)
	       minim=rq[i];
	for(i=sf*lun;i<=poz2;i++)
	    if(eulercost[i]<minim)
	       minim=eulercost[i];
	return minim;
}