Cod sursa(job #1163289)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 1 aprilie 2014 11:58:49
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include<fstream>
#include<vector>
#include<utility>
#include<iostream>

using namespace std;

#define max_n 32010
#define inf 200000

ifstream f("atac.in");
ofstream g("atac.out");

int n , m , q , A , B , C , D , X , Y , p;
int u , v , k , sol , nr , lca;

int Euler[25][4*max_n] , P[4*max_n];
int Nivel[max_n] , First[max_n];

pair<int , int> V[25][max_n];
vector< pair<int , int> > L[max_n];

void read(){

	f>>n>>m>>q;

	for( int i = 1 ; i < n ; i++ ){
		f>>u>>v;
		L[u].push_back( make_pair( i+1 , v ) );
		L[i+1].push_back( make_pair( u , v ) );
	}

	f>>X>>Y>>A>>B>>C>>D;

}

void print_graph(){

	for( int i = 1 ; i <= n ; i++ ){
		cout<<"^";
		for( int j = 0 ; j < L[i].size() ; j++ ){
			cout<<L[i][j].first<<" "<<L[i][j].second<<" | ";
		}
		cout<<"\n";
	}

}

void dfs( int nod , int niv , int tata ){

	Euler[0][++k] = nod;
	Nivel[nod] = niv;

	if( First[nod] == 0 )
		First[nod] = k;

	for( unsigned int j = 0 ; j < L[nod].size() ; j++ ){
		if( L[nod][j].first != tata ){
			V[0][L[nod][j].first] = make_pair( nod , L[nod][j].second );
			dfs( L[nod][j].first , niv + 1 , nod );
			Euler[0][++k] = nod;
		}
	}

}

void rmq(){

	for( int i = 2 ; i <= k ; i++ )
		P[i] = 1 + P[i/2];

	for( int i = 1 ; (1<<i) <= k ; i++ ){
		for( int j = 1 ; j <= (k - (1<<i) + 1) ; j++ )
		if( Nivel[ Euler[i-1][j] ] < Nivel[ Euler[i-1][j+(1<<(i-1))] ] )
			Euler[i][j] = Euler[i-1][j];
		else
			Euler[i][j] = Euler[i-1][j+(1<<(i-1))];
	}

	for( int i = 1 ; (1<<i) <= n ; i++ ){
		for( int j = 1 ; j <= n ; j++ ){
			V[i][j] = V[i-1][V[i-1][j].first];
			if( V[i][j].second > V[i-1][j].second )
				V[i][j].second = V[i-1][j].second;
		}
	}

}

int minim( int a , int b ){
	return a < b ? a : b;
}

void swap( int &x , int &y ){
	int aux = x; x = y; y = aux;
}

int Lca(){
	int x = First[X] , y = First[Y];
	if( x > y )
		swap( x , y );
	int p = P[ y - x + 1 ];
	return minim( Euler[p][x] , Euler[p][y - (1<<p) + 1] );
}

int find_sol(){

	lca = Lca();

	int x = X , y = Y , v_min = inf;

	while( x != lca ){
		p = P[ Nivel[lca] - Nivel[x] ];
		v_min = minim( v_min , V[p][x].second );
		x = V[p][x].first;
	}
	while( y != lca ){
		p = P[ Nivel[lca] - Nivel[y] ];
		v_min = minim( v_min , V[p][y].second );
		y = V[p][y].first;
	}

	return v_min;
}

void solve(){

	for( int i = 1 ; i <= m ; i++ ){

		sol = find_sol();

		if( i >= (m - q + 1) ){
			g<<sol<<"\n";
		}

		X = (X*A + Y*B) % n + 1;
		Y = (Y*C + sol*D) % n + 1;
	}

}

int main(){

	read();

	dfs( 1 , 1 , 0 );

	rmq();

	solve();

	return 0;
}