Cod sursa(job #251284)

Utilizator scvalexAlexandru Scvortov scvalex Data 2 februarie 2009 10:57:57
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <cstdio>
#include <vector>

using namespace std;

const int oo = 1<<30;

int N, M, P;

int cost[32001];
int T[32001];
vector<int> c[32001];
int L[32001];
int A[16][32001];
int minseg[16][32001];

void make_levels_go(int x, int lvl) {
	L[x] = lvl;
	for (vector<int>::iterator ii = c[x].begin(); ii != c[x].end(); ++ii)
		make_levels_go(*ii, lvl+1);
}

void make_levels() {
	make_levels_go(1, 0);
}

void make_ancestors() {
	int i, j;

	for (j = 0; (1<<j) < N; ++j)
		for (i = 1; i <= N; ++i)
			A[j][i] = -1;
	
	for (i = 1; i <= N; ++i)
		A[0][i] = T[i];
	
	for (j = 1; (1<<j) < N; ++j)
		for (i = 1; i <= N; ++i)
			if (A[j-1][i] != -1)
				A[j][i] = A[j-1][A[j-1][i]];
}

void calc_minsegs() {
	int i, j;

	for (i = 1; i <= N; ++i)
		minseg[0][i] = i;

	for (j = 1; (1<<j) < N; ++j)
		for (i = 1; i <= N; ++i)
			if (A[j-1][i] != -1) {
				if (cost[minseg[j-1][i]] < cost[minseg[j-1][A[j-1][i]]])
					minseg[j][i] = minseg[j-1][i];
				else
					minseg[j][i] = minseg[j-1][A[j-1][i]];
			}
}

int lca(int p, int q) {
	int aux, log, i;

	if (L[p] < L[q]) {
		aux = p;
		p = q;
		q = aux;
	}

	for (log = 0; (1<<log) <= L[p]; ++log)
		;
	--log;

	for (i = log; i >= 0; --i)
		if (L[p] - (1<<i) >= L[q])
			p = A[i][p];
	
	if (p == q)
		return p;
	
	for (i = log; i >= 0; --i)
		if ((A[i][p] != -1) && (A[i][p] != A[i][q])) {
			p = A[i][p];
			q = A[i][q];
		}
	
	return T[p];
}

int calc_minseg(int p, int l) {
	int m = oo, i;

	for (i = 0; (1<<i) <= l; ++i)
		;
	--i;

	for (; i >= 0; --i) {
		if (m > cost[minseg[i][p]]) {
			m = cost[minseg[i][p]];
			p = A[i][p];
		}
	}

	return m;
}

int main(int argc, char *argv[]) {
	int i, u, v, j, l;
	int X, Y, AA, BB, CC, DD, Z, z1, z2;

	FILE *fi = fopen("atac.in", "r");
	fscanf(fi, "%d %d %d", &N, &M, &P);
	for (i = 2; i <= N; ++i) {
		fscanf(fi, "%d %d", &u, &v);
		T[i] = u;
		c[u].push_back(i);
		cost[i] = v;
	}
	T[1] = -1;
	cost[1] = oo;

	make_levels();
	/*printf("Levels: ");
	for (i = 1; i <= N; ++i)
		printf("%d ", L[i]);
	printf("\n");*/

	make_ancestors();
	/*printf("Ancestors:\n");
	for (j = 0; (1<<j) < N; ++j) {
		for (i = 1; i <= N; ++i)
			printf("%2d ", A[j][i]);
		printf("\n");
	}*/

	calc_minsegs();
	/*printf("Minsegs:\n");
	for (j = 0; (1<<j) < N; ++j) {
		for (i = 1; i <= N; ++i)
			printf("%2d ", minseg[j][i]);
		printf("\n");
	}*/

	fscanf(fi, "%d %d %d %d %d %d", &X, &Y, &AA, &BB, &CC, &DD);
	FILE *fo = fopen("atac.out", "w");
	while (M--) {
		l = lca(X, Y);
		/*printf("%d %d -> %d\n", X, Y, l);*/
		z1 = calc_minseg(X, L[X] - L[l]);
		z2 = calc_minseg(Y, L[Y] - L[l]);
		/*printf("%d %d\n", z1, z2);*/

		Z = z1;
		if (z2 < Z)
			Z = z2;

		/*printf("Z = %d\n", Z);*/

		if (M < P) {
			fprintf(fo, "%d\n", Z);
		}
		X = (X*AA + Y*BB) % N + 1;
		Y = (Y*CC + Z*BB) % N + 1;
	}
	fclose(fo);
	fclose(fi);

	return 0;
}