Cod sursa(job #1861394)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 28 ianuarie 2017 20:43:05
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <vector>
#include <fstream>
#define INF 0x3f3f3f3f
#define NMAX 32005

using namespace std;

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

int cost[16][NMAX],anc[16][NMAX],d[NMAX],depthmax;
vector<int> v[NMAX];

void DFS(int x, int depth) {
	depthmax=max(depthmax,depth);
	d[x]=depth;
	for(auto it:v[x])
		DFS(it,depth+1);
}

int ansquery(int x, int y) {
	int dif,i,minact;
	if(d[x]>d[y]) swap(x,y);

	dif=d[y]-d[x];

	minact=INF;
	for(i=0;(1<<i)<=dif;++i) {
		if(dif&(1<<i)) {
			minact=min(minact,cost[i][y]);
			y=anc[i][y];
		}
	}

	for(i=15;i>=0;--i) {
		if(anc[i][x]!=anc[i][y]) {
			minact=min(minact,min(cost[i][x],cost[i][y]));
			x=anc[i][x];
			y=anc[i][y];
		}
	}

	if(x!=y) minact=min(minact,min(cost[0][x],cost[0][y]));
	if(minact==INF) minact=0;

	return minact;
}

int main() {
	int i,n,m,nr,aux,auxst,auxdr,pos,x,p,y,j,a,b,c,d,z,xaux,yaux;

	fin>>n>>m>>p;

	for(i=2;i<=n;++i) {
		fin>>x>>y;
		v[x].push_back(i);
		anc[0][i]=x;
		cost[0][i]=y;
	}

	DFS(1,0);

	for(i=1;i<16;++i) {
		for(j=1;j<=n;++j) {
			anc[i][j]=anc[i-1][anc[i-1][j]];
			cost[i][j]=min(cost[i-1][j],cost[i-1][anc[i-1][j]]);
		}
	}

	fin>>x>>y>>a>>b>>c>>d;
	for(i=1;i<=m;++i) {
		z=ansquery(x,y);

		if(i>=m-p+1) fout<<z<<'\n';

		x=(x*a+y*b)%n+1;
		y=(y*c+z*d)%n+1;
	}

	return 0;
}