Cod sursa(job #760440)

Utilizator GrimpowRadu Andrei Grimpow Data 21 iunie 2012 14:19:53
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<fstream>
using namespace std;
int T[20][32003],rq[20][32003];
int n,a,b,c,d,m,p,x,y,nr,L[32003],z,Sol[32003];
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);
void solve();
int min(int a,int b)
{
	if(a<b)
	 return a;
	else
	 return b;
 }
int main()
{
	citire();
	dfs(1);
	creeaza();
	solve();
}
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;
    L[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;
		   L[p->info]=L[k]+1;
		   dfs(p->info);
	    }
	}
}
void creeaza()
{
	for(int k=1;(1<<k)<n;k++)
	    for(int i=1;i<=n;i++)
	    {    
	        T[k][i]=T[k-1][T[k-1][i]];
	        rq[k][i]=min(rq[k-1][i],rq[k-1][T[k-1][i]]);
		}		   
}

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 lca(int x, int y)
{
	if(L[x] < L[y])
		swap(x, y);

	int log1=1, log2=1;
	for(; (1 << log1) < L[x]; ++log1);
	for(; (1 << log2) < L[y]; ++log2);

	for(int k = log1; k >= 0; --k)
		if(L[x] - (1 << k) >= L[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];
}

int dist(int x, int y)
{
	int sol=2147000000, lg=1;
	for(; (1 << lg) < L[x]; ++lg);

	for(int k = lg; k >= 0; --k)
		if(L[x] - (1 << k) >= L[y])
			sol = min(sol, rq[k][x]),
			x = T[k][x];

	return sol;
}

void solve()
{
	ofstream fout("atac.out");
	int z=0;
	for(int i = 1; i <= m; ++i)
	{
		int l = lca(x, y);
		
		if(x == y)
			z = 0;
		else	
			z = min(dist(x, l), dist(y, l));
		
		if(i > m-p)
			Sol[i-m+p] = z;
		x = ((x*a + y*b) % n) + 1;
		y = ((y*c + z*d) % n) + 1;
	}

	for(int i = 1; i <= p; ++i)
		fout << Sol[i] << "\n";
}