Pagini recente » Cod sursa (job #2816980) | Cod sursa (job #1627619) | Cod sursa (job #2745519) | Cod sursa (job #1999989) | Cod sursa (job #2634587)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
vector <pair <int, int>> v[32001];
int niv[32001];
int s[16][32001]; //s[i][j] = al 2^i-lea stramos al lui j
int rmq[16][32001]; //rmq[i][j] = costul minim al unei muchii in lantul de la nodul j la al 2^i-lea stramos al nodului j
void dfs(int r)
{
int i;
for (i = 0; i<v[r].size(); i++)
if (niv[v[r][i].first] == 0)
{
niv[v[r][i].first] = 1 + niv[r];
s[0][v[r][i].first] = r;
rmq[0][v[r][i].first] = v[r][i].second;
dfs(v[r][i].first);
}
}
int query(int x, int y)
{
if (x == y)
return 0;
if (niv[x] < niv[y])
swap(x, y);
//x este mai jos decat y
int d = niv[x] - niv[y], l;
int rasp = 1<<30;
for (l = 0; (1<<l) <= d; l++)
if (d & (1<<l))
{
rasp = min(rasp, rmq[l][x]);
x = s[l][x];
}
if (x == y)
return rasp;
l = 0;
while ((1<<l) <= niv[x])
l++;
while (l >= 0)
{
if (s[l][x] != 0 && s[l][x] != s[l][y])
{
rasp = min(rasp, rmq[l][x]);
rasp = min(rasp, rmq[l][y]);
x = rmq[l][x];
y = rmq[l][y];
}
l--;
}
rasp = min(rasp, rmq[0][x]);
rasp = min(rasp, rmq[0][y]);
return rasp;
}
int main()
{
int i, n, m, p, j;
int x, y, a, b, c, d, rasp;
fin >> n >> m >> p;
for (i = 2; i<=n; i++)
{
fin >> x >> y;
v[i].push_back({x, y});
v[x].push_back({i, y});
}
/*
for (i = 0; (1<<i) <= n; i++)
for (j = 0; j<=n; j++)
rmq[i][j] = 1<<30;*/
niv[1] = 1;
dfs(1);
for (i = 1; (1<<i) <= n; i++)
for (j = 1; j<=n; j++)
{
s[i][j] = s[i-1][s[i-1][j]];
rmq[i][j] = min(rmq[i-1][j], rmq[i-1][s[i-1][j]]);
}
fin >> x >> y >> a >> b >> c >> d;
for (i = 1; i<=m; i++)
{
rasp = query(x, y);
x = (1ll*x*a + 1ll*y*b)%n + 1;
y = (1ll*y*c + 1ll*rasp*d)%n + 1;
if (i >= m-p+1)
fout << rasp << '\n';
}
return 0;
}