Cod sursa(job #420021)

Utilizator otilia_sOtilia Stretcu otilia_s Data 18 martie 2010 12:46:01
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 32004
#define oo 100000
bool sch;
ofstream fout("atac.out");
int S[15][NMAX],Ct[15][NMAX];
int Niv[NMAX];
int N,M,P,X,Y,A,B,C,D,nx,ny;
vector < pair<int,int> > Ad[NMAX];

void citire()
{
	ifstream fin("atac.in");
	fin>>N>>M>>P;	
	int i;
	for (i=2;i<=N;++i)
	{ int x,c;
		fin>>x>>c;
		Ad[i].push_back( make_pair(x,c) );
		Ad[x].push_back( make_pair(i,c) );
	}
	fin>>X>>Y>>A>>B>>C>>D;
	fin.close();
}

void dfs(int x, int nv)
{
	Niv[x]=nv; 
	for (int i=0;i<Ad[x].size();++i)
	 if (Ad[x][i].first!=S[0][x])
	 {
	  S[0][Ad[x][i].first]=x; Ct[0][Ad[x][i].first]=Ad[x][i].second;
	  dfs(Ad[x][i].first,nv+1);
	 }
}

void LCA(int x, int y)
{   sch=0;
	if (Niv[x]<Niv[y]) { int aux=x; x=y; y=aux; sch=1;}
	int logx,logy;	
	for (logx=0;(1<<logx)<Niv[x];++logx) ;
	for (logy=0;(1<<logy)<Niv[y];++logy) ;
	
	nx=ny=0; int k;
	for (k=logx;k>=0;--k)
	 if (Niv[x]-(1<<k)>=Niv[y]) {x=S[k][x]; nx+=(1<<k);}
	
	if (x==y) return ;
	 
	for (k=logy; k>=0; --k)
	 if (S[k][x] && S[k][x]!=S[k][y])
		{
			x=S[k][x]; nx+=(1<<k);
			y=S[k][y]; ny+=(1<<k);
		}
	nx++; ny++;
	return ;
}

void nextpair(int &X, int &Y, int Z)
{ int X2;
	X2 = (X*A + Y*B) % N + 1;
	Y = (Y*C + Z*D) % N + 1;
	X=X2;
}

int dist(int x, int nx)
{
	int cmin=oo, k;
	k=0;
	while (nx>=(1<<k)) ++k;
	--k;
	while (k>=0)
	 {
	  if ((1<<k)&nx) 
		{
			cmin=min(cmin,Ct[k][x]);
			x=S[k][x];			
	    }
	  --k;
	 }
    return cmin;
}

int main()
{
	citire();
	
	dfs(1,0);
	int k,i;
	for (k=1;(1<<k)<=N;++k)
	 for (i=1;i<=N;++i)
	  { S[k][i]=S[k-1][S[k-1][i]];
	    Ct[k][i]=min(Ct[k-1][S[k-1][i]],Ct[k-1][i]);
	  }
	 
	for (int test=1;test<=M;++test)
	{
		if (X==Y) { 
		            if (test>M-P+1) fout<<"0\n";
					nextpair(X,Y,0);
					continue;
		          }
		LCA(X,Y);			

		if (sch) { int aux=nx; nx=ny; ny=aux;}
		int Z=min(dist(X,nx),dist(Y,ny));		
		
		if (test>=M-P+1) fout<<Z<<"\n";
				
		nextpair(X,Y,Z);		
	}

	return 0;
}