Pagini recente » Cod sursa (job #1776832) | Cod sursa (job #1909685) | Cod sursa (job #2507214) | Cod sursa (job #1595860) | Cod sursa (job #2266719)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
#define Inf 0x3f3f3f
#define MAX 32001
#define LOGMAX 20
int nro, m, p, X, Y, A, B, C, D;
vector< vector<int> > G;
vector< vector<int> > rmq, rmqg, v;
vector< pair<int, int> > dad;
vector<int> Se, fap, lvl;
vector<bool> viz;
void Read();
int CalcMin(int x, int y);
int Lca (int x, int y);
void Dfs(int, int);
void Rmq();
void RmqG();
void Init();
int main()
{
Read();
Dfs(1, 1);
Rmq();
RmqG();
for (int i = 1, x = X, y = Y; i <= m; i ++)
{
int aux = x, auy = y, z;
int lca = Lca(x, y);
z = min(CalcMin(x, lca), CalcMin(y, lca));
if (z == Inf)z = 0;
x = (aux * A + auy * B) % nro + 1;
y = (auy * C + z * D) % nro + 1;
if (i >= m - p + 1)
fout << z << '\n';
}
return 0;
}
void Read()
{
fin >> nro >> m >> p;
G = vector< vector<int> >(/*nro + 1*/MAX);
viz = vector<bool>(/*nro + 1*/MAX, 0);
fap = vector<int>(/*nro + 1*/MAX);
dad = vector< pair<int, int> >(/*nro + 1*/MAX);
for (int i = 2, x, v; i <= nro; i ++)
{
fin >> x >> v;
G[i].push_back(x);
G[x].push_back(i);
dad[i] = {x, v};
}
fin >> X >> Y >> A >> B >> C >> D;
}
int CalcMin(int x, int y)
{
if (x == y)return Inf;
int k = log2(lvl[x] - lvl[y]);
return min(rmqg[k][x], CalcMin(v[k][x], y));
}
int Lca (int x, int y)
{
if (x == y)return x;
x = fap[x];
y = fap[y];
if (x > y)swap(x, y);
int l = log2(y - x + 1);
if (lvl[rmq[l][x]] < lvl[rmq[l][y - (1 << l)]])
return Se[rmq[l][x]];
else return Se[rmq[l][y - (1 << l)]];
}
void Dfs(int node, int l)
{
viz[node] = 1;
Se.push_back(node);
lvl.push_back(l);
fap[node] = Se.size();
for (int i = 0; i < G[node].size(); i ++)
{
if (!viz[G[node][i]])Dfs(G[node][i], l + 1);
Se.push_back(node);
lvl.push_back(l);
}
}
void Rmq()
{
int k = Se.size();
rmq = vector< vector<int> >(/*log2(k) + 2*/LOGMAX, vector<int>(/*nro + 1*/MAX));
for (int i = 0; i < k; i ++)
rmq[0][i] = i;
for (int i = 1; (1 << i) < k; i ++)
for (int j = 1; j <= k - (1 << i); j ++)
{
int l = 1 << (i - 1);
rmq[i][j] = rmq[i - 1][j];
if(lvl[rmq[i - 1][j + l]] < lvl[rmq[i][j]])
rmq[i][j] = rmq[i - 1][j + l];
}
}
void RmqG()
{
int k = log2(nro);
rmqg = vector< vector<int> >(/*k + 2*/LOGMAX, vector<int>(/*nro + 1*/MAX, Inf));
v = vector< vector<int> >(/*k + 2*/LOGMAX, vector<int>(/*nro + 1*/MAX));
for (int i = 1; i <= nro; i ++)
{
v[0][i] = dad[i].first;
rmqg[0][i] = dad[i].second;
}
for (int i = 1; i <= k; i ++)
for (int j = 1; j <= nro; j ++)
{
v[i][j] = v[i - 1][v[i - 1][j]];
rmqg[i][j] = min(rmqg[i - 1][j], rmqg[i - 1][v[i - 1][j]]);
}
}