Cod sursa(job #1129674)

Utilizator raulstoinStoin Raul raulstoin Data 28 februarie 2014 01:48:14
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
#include<vector>
#include<algorithm>

#define NMAX 32005
#define MMAX
#define L depth.size()
#define ANCESTOR depth[L-1-(1<<(i-1))]

using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

short TT[17][NMAX];
int n,m,p,k,X,Y,a,b,c,d,v[NMAX],mins[17][NMAX],first[NMAX];
int euler[2*NMAX],lca_rmq[17][2*NMAX],level[2*NMAX],Log[2*NMAX],Lev[NMAX];
vector<short> G[NMAX],depth;
vector<int> sol;

void read()
{
	fin>>n>>m>>p;
	for(int i=2,x;i<=n;i++)
	{
		fin>>x>>v[i];
		G[x].push_back(i);
	}
	fin>>X>>Y>>a>>b>>c>>d;
}

void DFS(short nod,short niv,int tt)
{
	depth.push_back(nod);
	euler[++k]=nod;
	first[nod]=k;
	level[k]=niv;
	Lev[nod]=niv;
	
	mins[0][nod]=v[nod];
	TT[0][nod]=tt;
	for(size_t i=1;(1U<<i)<depth.size();i++)
	{
		mins[i][nod]=min(mins[i-1][nod],mins[i-1][ANCESTOR]);
		TT[i][nod]=TT[i-1][ANCESTOR];
	}
	
	for(size_t i=0;i<G[nod].size();i++)
	{
		DFS(G[nod][i],niv+1,nod);
		euler[++k]=nod;
		level[k]=niv;
	}
	depth.pop_back();
}

void lca_rmq_build()
{
	for(int i=2;i<=k;i++)
		Log[i]=Log[i/2]+1;
	for(int i=1;i<=k;i++)
		lca_rmq[0][i]=i;
	for(int i=1,p=(1<<i);p<k;i++,p<<=1)
		for(int j=1;j<=k-p;j++)
			if(level[lca_rmq[i-1][j+p/2]]<level[lca_rmq[i-1][j]])
				lca_rmq[i][j]=lca_rmq[i-1][j+p/2];
			else
				lca_rmq[i][j]=lca_rmq[i-1][j];
}

inline short query_lca(int x,int y)
{
	if(x>y)
		swap(x,y);
	int dif=y-x+1,line=Log[dif],plus=dif-(1<<line);
	if(level[lca_rmq[line][x+plus]]<level[lca_rmq[line][x]])
		return euler[lca_rmq[line][x+plus]];
	return euler[lca_rmq[line][x]];
}

int main()
{
	read();
	DFS(1,0,0);
	lca_rmq_build();
	for(;m;m--)
	{
		int LCA=query_lca(first[X],first[Y]),Z=(1<<30),x=X,y=Y;
		for(int i=Lev[X]-Lev[LCA];i;i-=(1<<Log[i]))
		{
			Z=min(Z,mins[Log[i]][X]);
			X=TT[Log[i]][X];
		}
		for(int i=Lev[Y]-Lev[LCA];i;i-=(1<<Log[i]))
		{
			Z=min(Z,mins[Log[i]][Y]);
			Y=TT[Log[i]][Y];
		}
		if(x==y)
			Z=0;
		X=(x*a+y*b)%n+1;
		Y=(y*c+Z*d)%n+1;
		sol.push_back(Z);
	}
	for(size_t i=sol.size()-p;i<sol.size();i++)
		fout<<sol[i]<<'\n';
	return 0;
}