Cod sursa(job #1140858)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 12 martie 2014 12:25:11
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <fstream>
#include <vector>
using namespace std;
int n, m, P, X, Y, A, B, C, D, sz, sol;
int level[33000], euler[66000], adancime[66000], rmq[17][66000], poz[17][66000], poznod[33000];
int best[17][33000], stramos[17][33000], sus[33000], tata[33000], loga[66000];
struct Muchie
{
	int x, c;
	Muchie()
	{
		x = c = 0;
	}
	Muchie(int xx, int cc)
	{
		x = xx;
		c = cc;
	}
};
vector <Muchie> G[100100];
bool viz[100100];

inline void DFS(int x, int lvl)
{
	int nod, cost;
	level[x] = lvl;
	viz[x] = true;
	vector <Muchie>::iterator it;
	for(it = G[x].begin(); it != G[x].end(); ++it)
	{
		nod = (*it).x;
		cost = (*it).c;
		if(!viz[nod])
		{
			sus[nod] = cost;
			tata[nod] = x;
			sz++;
			euler[sz] = x;
			adancime[sz] = level[x];
			DFS(nod, lvl + 1);
		}
	}
	sz++;
	euler[sz] = x;
	adancime[sz] = level[x];
	poznod[x] = sz;
}

inline void PrecalcLCA()
{
	int i, k;
	loga[1] = 0;
	for(i = 2; i < 66000; ++i)
		loga[i] = loga[i / 2] + 1;
	for(i = 1; i <= sz; ++i)
	{
		rmq[0][i] = adancime[i];
		poz[0][i] = i;
	}
	for(k = 1; (1 << k) <= sz; ++k)
	{
		for(i = 1; i + (1 << k) - 1 <= sz; ++i)
		{
			if(rmq[k - 1][i] < rmq[k - 1][i + (1 << (k - 1))])
			{
				rmq[k][i] = rmq[k - 1][i];
				poz[k][i] = poz[k - 1][i];
			}
			else
			{
				rmq[k][i] = rmq[k - 1][i + (1 << (k - 1))];
				poz[k][i] = poz[k - 1][i + (1 << (k - 1))];
			}
		}
	}
}

inline void PrecalcBest()
{
	int i, k, hmax = 0;
	for(i = 1; i <= n; ++i)
	{
		best[0][i] = sus[i];
		stramos[0][i] = tata[i];
	}
	for(i = 1; i <= n; ++i)
		hmax = max(hmax, level[i]);
	for(k = 1; (1 << k) <= hmax; ++k)
	{
		for(i = 1; i <= n; ++i)
		{
			if((1 << k) + 1 <= level[i])
			{
				best[k][i] = min(best[k - 1][i], best[k - 1][stramos[k - 1][i]]);
				stramos[k][i] = stramos[k - 1][stramos[k - 1][i]];
			}
		}
	}
}

inline int Solve(int X, int Y)
{
	if(X == Y)
		return 0;
	int st, dr, k, lca, lg, rez = 1000000000;
	st = min(poznod[X], poznod[Y]);
	dr = max(poznod[X], poznod[Y]);
	k = loga[dr - st + 1];
	if(rmq[k][st] < rmq[k][st + (dr - st + 1 - (1 << k))])
		lca = euler[poz[k][st]];
	else
		lca = euler[poz[k][st + (dr - st + 1 - (1 << k))]];
	lg = level[X] - level[lca];
	while(X != lca)
	{
		k = loga[lg];
		rez = min(rez, best[k][X]);
		X = stramos[k][X];
		lg -= (1 << k);
	}
	lg = level[Y] - level[lca];
	while(Y != lca)
	{
		k = loga[lg];
		rez = min(rez, best[k][Y]);
		Y = stramos[k][Y];
		lg -= (1 << k);
	}
	return rez;
}

int main()
{
	int i, x, y, cost;
	ifstream fin("atac.in");
	fin >> n >> m >> P;
	for(i = 2; i <= n; ++i)
	{
		fin >> x >> cost;
		G[i].push_back(Muchie(x, cost));
		G[x].push_back(Muchie(i, cost));
	}
	fin >> X >> Y >> A >> B >> C >> D;
	fin.close();
	
	DFS(1, 1);
	PrecalcLCA();
	PrecalcBest();
	
	ofstream fout("atac.out");
	sol = Solve(X, Y);
	for(i = 2; i <= m; ++i)
	{
		x = (1LL * X * A + 1LL * Y * B) % n + 1;
		y = (1LL * Y * C + 1LL * sol * D) % n + 1;
		X = x;
		Y = y;
		sol = Solve(X, Y);
		if(i > m - P)
			fout << sol << "\n";
	}
	fout.close();
	return 0;
}