Cod sursa(job #573106)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 5 aprilie 2011 21:44:13
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include<stdio.h>
#include<vector>

#define maxN 32005
#define maxLog 17
#define INF 1 << 29

using namespace std;

FILE*f=fopen("atac.in","r");
FILE*g=fopen("atac.out","w");

int n,m,p,i,a,cst,j,k,X,Y,A,B,C,D,lca,nivmax,Str[maxLog][maxN],Din[maxLog][maxN],Min;
int Eul[maxN<<1],Fap[maxN],Viz[maxN],Niv[maxN<<1],rmq[maxLog][maxN<<1],E[maxN<<1],Dist[maxN];

vector< pair<int,int> >G[maxN];

void dfs( int nod , int niv ){
	
	if ( niv > nivmax )	nivmax = niv;
	
	Eul[++k] = nod;
	Niv[k] = niv;
	Fap[nod] = k;
	Dist[nod] = niv;
	Viz[nod] = 1;
	
	for ( int i = 0 ; i < G[nod].size() ; ++i ){
		int vcn = G[nod][i].first;
		if ( !Viz[vcn] ){
			Str[0][vcn] = nod;
			Din[0][vcn] = G[nod][i].second;
			dfs(vcn,niv+1);
			Eul[++k] = nod;
			Niv[k] = niv;
		}
	}
	
}

inline void RMQ () {
	
	for ( i = 2 ; i <= k ; ++i ){
		E[i] = E[i>>1] + 1;
	}
	
	for ( i = 1 ; i <= k ; ++i ){
		rmq[0][i] = i;
	}
	
	for ( j = 1 ; j <= E[k] ; ++j ){
		
		for ( i = 1 ; i + ( 1 << j ) - 1 <= k ; ++i ){
			
			rmq[j][i] = Niv[ rmq[j-1][i] ] < Niv[  rmq[j-1][i+( 1<< (j-1) )] ] ? rmq[j-1][i] : rmq[j-1][i+(1<<(j-1))];
			
		}
		
	}
	
}

int LCA ( int x, int y ){
	
	if ( Fap[x] > Fap[y] ) swap(x,y);
	
	int e = E[Fap[y] - Fap[x]+1];
	
	int lowestca = Niv[ rmq[e][Fap[x]] ] < Niv[ rmq[e][Fap[y] - ( 1 << e )+1] ] ? rmq[e][Fap[x]] : rmq[e][Fap[y] - ( 1 << e )+1] ;
	
	return Eul[lowestca];
	
}

void fct ( int nod , int dist ){
	
	int P = 0;
	
	while ( dist ){
		if ( dist & 1 ){
			Min = min(Min,Din[P][nod]);
			nod = Str[P][nod];
		}
		++P;
		dist = dist >> 1;
	}
	
	
}

int main () {
	
	fscanf(f,"%d %d %d",&n,&m,&p);
	
	for ( i = 2 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&a,&cst);
		G[i].push_back(make_pair(a,cst));
		G[a].push_back(make_pair(i,cst));
	}
	
	fscanf(f,"%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
	
	dfs(1,0);
	
	RMQ();
	
	for ( j = 1 ; j <= E[nivmax]; ++j )
		for ( i = 1 ; i <= n ; ++i )
			Din[j][i] = INF;
	
	for ( j = 1 ; j <= E[nivmax] ; ++j ){
		
		for ( i = 1 ; i <= n ; ++i ){
			
			Str[j][i] = Str[j-1][Str[j-1][i]];
			
			Din[j][i] = min(Din[j-1][i],Din[j-1][Str[j-1][i]]);
			
		}
		
	}
	
	for ( i = 1 ; i <= m ; ++i ){
		
		if ( X == Y ){
			fprintf(g,"0\n");
			continue ;
		}
		
		lca = LCA(X,Y);
		
		int d1 = Dist[X]-Dist[lca];
		int d2 = Dist[Y]-Dist[lca];
		
		Min = INF;
		
		fct(X,d1);
		fct(Y,d2);
		
		if ( i > m - p ) fprintf(g,"%d\n",Min);
		
		X = ( X * A + Y * B ) % n + 1;
		Y = ( Y * C + Min * D ) % n + 1;
		
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}