Cod sursa(job #2123908)

Utilizator vancea.catalincatalin vancea.catalin Data 6 februarie 2018 18:41:14
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<iostream>
#include<fstream>
#include<vector>
#define DN 32100
#define MAXX 320100

using namespace std;
fstream fin("atac.in",ios::in), fout("atac.out",ios::out);
vector<pair<int,int> > v[DN];
int N,M,P,A,B,C,D,x,y,z;
int le,euler[2*DN],f[2*DN],l[2*DN],rmq[17][2*DN],log[2*DN];

void dfs(int nod)
{
	f[nod]=le;
	for(auto x:v[nod])
	{
		//nod->x
		rmq[0][le]=x.second;	
		euler[++le]=x.first;
		
		dfs(x.first);
		
		//x->nod
		rmq[0][le]=x.second;
		euler[++le]=nod;
	}
	l[nod]=le;
	rmq[0][le]=MAXX;
}
int lca(int x,int y)
{
	int dif;
	
	if(l[x]>f[y]) swap(x,y);
	
	//minimul din intervalul l[x] f[y] 
	dif=f[y]-l[x];
	dif=log[dif];
	
	return min(rmq[dif][l[x]],rmq[dif][f[y]-(1<<dif)]);
}

int main()
{
	int i,j,U,V,lim;
	fin>>N>>M>>P;
	for(i=2;i<=N;i++){   
		//u->i cost v
		fin>>U>>V;
		v[U].push_back({i,V});
	}
	euler[le=1]=1;
	
	dfs(1);
	
	for(i=1;(1<<i)<=le;i++)
	{
		lim=le-(1<<i);
		for(j=1;j<=lim;j++)
		{
			rmq[i][j]=min(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
		}
	}
	for(i=0;(1<<i)<2*DN;i++) log[1<<i]=i;
	for(i=1;i<2*DN;i++) log[i]=max(log[i-1],log[i]);
	
	fin>>x>>y>>A>>B>>C>>D;
	
	for(i=1;i<=M;i++)
	{
		
		z=lca(x,y);
		//cout<<i<<": "<<x<<" "<<y<<" "<<z<<"\n";
		
		if(M-P<i)
		{
			fout<<z<<"\n";
		}
		x=(x*A + y*B)%N+1;
		y=(y*C + z*D)%N+1;
		
	}	
	
}