Pagini recente » Cod sursa (job #845664) | Cod sursa (job #1293068) | Istoria paginii utilizator/cacatpansat3213 | Cod sursa (job #2072643) | Cod sursa (job #2655985)
#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;
}
}