Cod sursa(job #1129637)

Utilizator raulstoinStoin Raul raulstoin Data 28 februarie 2014 00:28:44
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
#include<vector>
#include<algorithm>

#define NMAX 32005
#define MMAX
#define L depth.size()

using namespace std;

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

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<int> G[NMAX],depth,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;
	v[1]=(1<<30);
}

void DFS(short nod,short niv)
{
	depth.push_back(v[nod]);
	euler[++k]=nod;
	first[nod]=k;
	level[k]=niv;
	Lev[nod]=niv;
	for(size_t i=0;i<G[nod].size();i++)
	{
		DFS(G[nod][i],niv+1);
		euler[++k]=nod;
		level[k]=niv;
	}
	mins[0][nod]=v[nod];
	for(size_t i=1;(1U<<i)<depth.size();i++)
		mins[i][nod]=min(mins[i-1][nod],depth[L-(1<<i)]);
	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];
}

short query_lca(short x,short 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);
	lca_rmq_build();
	for(;m;m--)
	{
		int LCA=query_lca(first[X],first[Y]),Z=(1<<30);
		for(int i=Lev[X]-Lev[LCA];i;i-=(1<<Log[i]))
			Z=min(Z,mins[Log[i]][X]);
		for(int i=Lev[Y]-Lev[LCA];i;i-=(1<<Log[i]))
			Z=min(Z,mins[Log[i]][Y]);
		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;
}