Cod sursa(job #375164)

Utilizator ProtomanAndrei Purice Protoman Data 19 decembrie 2009 18:00:15
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define MAX 32010
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

vector <pair <int, int> > vctEuler;
vector <pair <int, int> > vctDrum[MAX];
pair <int, int> logStr[MAX][20];
int rmqLCA[2 * MAX][20];
int poz[MAX], sel[MAX];
int n, m, p, a, b, c, d, x, y, sol;

inline void euler(int nod, int depth)
{
	sel[nod] = 1;

	vctEuler.pb(mp(depth, nod));
	for (int i = 0; i < vctDrum[nod].size(); i++)
		if (!sel[vctDrum[nod][i].f])
		{
			euler(vctDrum[nod][i].f, depth + 1);
			vctEuler.pb(mp(depth, nod));
		}
		else logStr[nod][0] = mp(vctDrum[nod][i].s, vctDrum[nod][i].f);
}

inline void calcStr(int nod)
{
	int str = logStr[nod][0].s, k = 1;

	for (; str; str = logStr[str][k - 1].s, k++)
		logStr[nod][k] = mp(min(logStr[nod][k - 1].f, logStr[str][k - 1].f), logStr[str][k - 1].s);
}

inline int extrMin(int nod, int ad)
{
	int minGs = LONG_MAX;
	for (int i = 19; i >= 0; i--)
		if (ad >= (1 << i))
		{
			minGs = min(minGs, logStr[nod][i].f);
			nod = logStr[nod][i].second;
			ad -= (1 << i);
		}

	return minGs;
}

int main()
{
	freopen("atac.in", "r", stdin);
	freopen("atac.out", "w", stdout);
	
	scanf("%d %d %d", &n, &m, &p);

	for (int i = 2; i <= n; i++)
	{
		int nod, cost;
		scanf("%d %d", &nod, &cost);

		vctDrum[i].pb(mp(nod, cost));
		vctDrum[nod].pb(mp(i, cost));
	}

	scanf("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d);

	vctEuler.pb(mp(0, 0));
	euler(1, 1);
	int lung = vctEuler.size() - 1;

	for (int i = 1; i <= lung; i++)
		if (!poz[vctEuler[i].s])
		{
			poz[vctEuler[i].s] = i;
			calcStr(vctEuler[i].s);
		}

	for (int i = 1; i <= lung; i++)
		rmqLCA[i][0] = i;
	for (int mas = 1, k = 1; mas <= lung; mas *= 2, k++)
		for (int i = 1; i + mas - 1 <= lung; i++)
		{
			rmqLCA[i][k] = rmqLCA[i][k - 1];
			if (vctEuler[rmqLCA[i][k - 1]].f > vctEuler[rmqLCA[i + mas][k - 1]].f)
				rmqLCA[i][k] = rmqLCA[i + mas][k - 1];
		}

	for (; m; m--)
	{
		int st = poz[x];
		int fn = poz[y];
		if (st > fn)
			swap(st, fn);

		int mas = 1, k = 0;
		for (; mas * 2 <= fn - st; mas *= 2, k++);

		int locMin = rmqLCA[st][k];
		if (vctEuler[rmqLCA[st][k]].f > vctEuler[rmqLCA[fn - mas + 1][k]].f)
			locMin = rmqLCA[fn - mas + 1][k];

		int adMax = vctEuler[locMin].f;
		sol = min(extrMin(x, vctEuler[poz[x]].f - adMax), extrMin(y, vctEuler[poz[y]].f - adMax));

		if (x == y)
			sol = 0;
		if (m <= p)
			printf("%d\n", sol);
		x = (a * x + b * y) % n + 1;
		y = (c * y + d * sol) % n + 1;
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}