Cod sursa(job #2655985)

Utilizator sebimihMihalache Sebastian sebimih Data 6 octombrie 2020 13:37:12
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N = 32005, LOG = 15, inf = 1e6;

int n;
vector<int> g[N];
int rmq[LOG][N], anc[LOG][N], lvl[N];

void df(int nod, int nivel)
{
	lvl[nod] = nivel;

	for (int neigh : g[nod])
	{
		df(neigh, nivel + 1);
	}
}

void precompute()
{
	df(1, 0);

	for (int p = 1; (1 << p) <= n; p++)
	{
		for (int i = 1; i <= n; i++)
		{
			anc[p][i] = anc[p - 1][anc[p - 1][i]];
			rmq[p][i] = min(rmq[p - 1][i], rmq[p - 1][anc[p - 1][i]]);
		}
	}
}

int SolveQuery(int x, int y)
{
	if (x == y)
	{
		return 0;
	}

	int ans = inf;

	if (lvl[x] < lvl[y])
	{
		swap(x, y);
	}

	int dif = lvl[x] - lvl[y];

	// Aducem pe acelasi nivel
	for (int i = 0; i < LOG; i++)
	{
		if (dif & (1 << i))
		{
			ans = min(ans, rmq[i][x]);
			x = anc[i][x];
		}
	}

	// Urcam pana la cel mai mic stramos comun
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (anc[i][x] != anc[i][y])
		{
			ans = min(ans, rmq[i][x]);
			ans = min(ans, rmq[i][y]);
			x = anc[i][x];
			y = anc[i][y];
		}
	}

	if (x != y)
	{
		ans = min(ans, rmq[0][x]);
		ans = min(ans, rmq[0][y]);
	}

	return ans;
}

int main()
{
	int m, p;
	fin >> n >> m >> p;

	for (int i = 2; i <= n; i++)
	{
		int x, cost;
		fin >> x >> cost;
		g[x].push_back(i);
		rmq[0][i] = cost;
		anc[0][i] = x;
	}

	precompute();

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

		if (i > m - p)
		{
			fout << z << '\n';
		}

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