Cod sursa(job #251034)

Utilizator tvladTataranu Vlad tvlad Data 1 februarie 2009 17:51:50
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <vector>
using namespace std;

const int N_MAX = 32000;
const int logN = 16;
const int aIntSize = 1 << logN;

int n,m,p, x,y,z, A,B,C,D;
vector< pair<int,int> > G[N_MAX];
int aInt[aIntSize+1];
int level[N_MAX];
int str[N_MAX][logN];
int mmin[N_MAX][logN];
vector<int> stack;

void aint_insert ( int cur, int st, int en, int x, int w ) {
	if (st == x && x == en) {
		aInt[cur] = w;
		return;
	}
	int m = st + (en-st)/2;
	if (x <= m) aint_insert(cur*2,st,m,x,w);
	if (x > m) aint_insert(cur*2+1,m+1,en,x,w);
	aInt[cur] = min(aInt[cur*2],aInt[cur*2+1]);
}

int aint_query ( int cur, int st, int en, int ist, int ien ) {
	if (ist <= st && en <= ien)
		return aInt[cur];
	int m = st + (en-st)/2;
	int r1 = 0x3f3f3f3f, r2 = 0x3f3f3f3f;
	if (ist <= m) r1 = aint_query(cur*2,st,m,ist,ien);
	if (ien > m) r2 = aint_query(cur*2+1,m+1,en,ist,ien);
	return min(r1,r2);
}

void df ( int k, int in_weight ) {
	level[k] = stack.size();
	stack.push_back(k);
	if (in_weight > -1) aint_insert(1,1,n,level[k],in_weight);
	for (int i = 0; (1 << i) <= level[k]; ++i) {
		str[k][i] = stack[level[k] - (1 << i)];
		mmin[k][i] = aint_query(1,1,n,level[k] - (1 << i) + 1, level[k]);
	}
	for (vector< pair<int,int> >::iterator i = G[k].begin(); i != G[k].end(); ++i) {
		if (level[i->first] == -1) {
			df(i->first,i->second);
		}
	}
	stack.pop_back();
}

void precalc() {
	for (int i = 0; i < n; ++i) level[i] = -1;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < logN; ++j)
			mmin[i][j] = 0x3f3f3f3f;
	for (int i = 0; i <= aIntSize; ++i) aInt[i] = 0x3f3f3f3f;
	df(0,-1);
}

int trace ( int &nod, int d ) {
	int m = 0x3f3f3f3f;
	for (int i = 0; (1 << i) <= d; ++i) {
		m = min(m,mmin[nod][i]);
		d -= (1 << i);
		nod = str[nod][i];
	}
	return m;
}

int solve ( int x, int y ) {
	if (level[x] > level[y]) x ^= y ^= x ^= y;
	int m = trace(y,level[y]-level[x]), lvl = level[x];
	int step;
	for (step = 1; (1 << (step + 1)) <= lvl; ++step);
	for (; step >= 0; --step) {
		if (str[x][step] != str[y][step]) {
			m = min(m,mmin[x][step]);
			x = str[x][step];
			m = min(m,mmin[y][step]);
			y = str[y][step];
		}
	}
	m = min(m,mmin[x][0]);
	m = min(m,mmin[y][0]);
	x = str[x][0];
	y = str[y][0];
	return m;
}

int main() {
	freopen("atac.in","rt",stdin);
	freopen("atac.out","wt",stdout);
	scanf("%d %d %d",&n,&m,&p);
	for (int i = 1; i < n; ++i) {
		int b, v;
		scanf("%d %d",&b,&v);
		--b;
		G[i].push_back(make_pair(b,v));
		G[b].push_back(make_pair(i,v));
	}
	scanf("%d %d %d %d %d %d",&x,&y,&A,&B,&C,&D);
	--x; --y;

	precalc();

	for (; m; --m) {
		z = solve(x,y);
		if (m <= p) printf("%d\n",z);
		++x; ++y;
		x = (x*A + y*B)%n;
		y = (y*C + z*D)%n;
	}

	return 0;
}