Cod sursa(job #568439)

Utilizator ChallengeMurtaza Alexandru Challenge Data 31 martie 2011 10:51:20
Problema Atac Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <vector>

using namespace std;

const char InFile[]="atac.in";
const char OutFile[]="atac.out";
const int MaxN=1<<15;
const int MaxM=1<<19;
const int LogMaxN=16;
const int INF=1<<30;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_edge
{
	s_edge(int _y=0, int _w=0):y(_y),w(_w){}
	int y,w;
};

int N,M,P,u,v,k,X,Y,A,B,C,D,Q[MaxM],niv[MaxN],T[LogMaxN][MaxN],W[LogMaxN][MaxN],lg[MaxN],viz[MaxN];
vector<s_edge> G[MaxN];

void DFS(int nod, int t)
{
	if(viz[nod])
	{
		return;
	}
	niv[nod]=k;
	++k;
	viz[nod]=1;
	T[0][nod]=t;
	for(vector<s_edge>::iterator it=G[nod].begin();it!=G[nod].end();++it)
	{
		if(t!=it->y)
		{
			DFS(it->y,nod);
		}
		else
		{
			W[0][nod]=it->w;
		}
	}
	--k;
}

inline void preprocesare()
{
	W[0][1]=INF;
	
	for(register int i=2;i<=N;++i)
	{
		lg[i]=lg[i>>1]+1;
	}
	
	for(register int i=1;i<LogMaxN;++i)
	{
		for(register int j=1;j<=N;++j)
		{
			T[i][j]=T[i-1][T[i-1][j]];
			W[i][j]=min(W[i-1][j],W[i-1][T[i-1][j]]);
		}
	}
}

inline int query(int x,int y)
{
	if(x==y)
	{
		return 0;
	}
	int w=INF;
	if(niv[x]<niv[y])
	{
		swap(x,y);
	}
	while(niv[x]!=niv[y])
	{
		int k=lg[niv[x]-niv[y]];
		w=min(w,W[k][x]);
		x=T[k][x];
	}
	int k=LogMaxN-1;
	while(x!=y)
	{
		while(k>-1 && T[k][x]==T[k][y])
		{
			--k;
		}
		if(k==-1)
		{
			w=min(w,W[0][x]);
			w=min(w,W[0][y]);
			break;
		}
		w=min(w,W[k][x]);
		w=min(w,W[k][y]);
		x=T[k][x];
		y=T[k][y];
	}
	return w;
}

int main()
{
	fin>>N>>M>>P;
	for(register int i=2;i<=N;++i)
	{
		fin>>u>>v;
		G[i].push_back(s_edge(u,v));
		G[u].push_back(s_edge(i,v));
	}
	fin>>X>>Y>>A>>B>>C>>D;
	fin.close();
	
	DFS(1,0);
	preprocesare();
	for(register int i=1;i<=M;++i)
	{
		int Z=query(X,Y);
		Q[++Q[0]]=Z;
		int Xprim=(X*A+Y*B)%N+1;
		int Yprim=(Y*C+Z*D)%N+1;
		X=Xprim;
		Y=Yprim;
	}
	
	for(register int i=Q[0]-P+1;i<=Q[0];++i)
	{
		fout<<Q[i]<<"\n";
	}
	fout.close();
	return 0;
}