Pagini recente » Cod sursa (job #327769) | Istoria paginii runda/cei_mai_mari_olimpicari_runda_1 | Cod sursa (job #3149239) | Cod sursa (job #470714) | Cod sursa (job #1690114)
#include <fstream>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
#define N 32005
#define LOGN 17
#define INF 2147483647
int n, m, p;
int t[N], cost[N];
int X, Y, A, B, C, D;
int lst[N], vf[N], urm[N], nvf = 0;
int e[2 * N], ne = 0, poz[N];
int nivel[N], niv = 0;
int r[2 * N][LOGN];
int lg[2 * N];
int str[N][LOGN];
int coststr[N][LOGN];
inline void euler(int x)
{
nivel[x] = ++niv;
e[++ne] = x;
poz[x] = ne;
for(int i = lst[x]; i; i = urm[i])
{
euler(vf[i]);
e[++ne] = x;
}
--niv;
}
inline int minim(int x, int y)
{
return (nivel[x] < nivel[y]) ? x : y;
}
inline int minim2(int x, int y)
{
return x < y ? x : y;
}
inline int drumMinim(int &x, int &y)
{
int pozx = poz[x];
int pozy = poz[y];
if(pozx > pozy)
swap(pozx, pozy);
int l = lg[pozy - pozx + 1];
int lca = minim(r[pozx][l], r[pozy - (1 << l) + 1][l]);
int c1 = INF, c2 = INF;
int xaux = x, yaux = y;
int dif = nivel[x] - nivel[lca];
int j = 0;
while(dif != 0)
{
if(dif & 1)
{
c1 = minim2(c1, coststr[x][j]);
x = str[x][j];
}
dif >>= 1;
j++;
}
dif = nivel[y] - nivel[lca];
j = 0;
while(dif != 0)
{
if(dif & 1)
{
c2 = minim2(c2, coststr[y][j]);
y = str[y][j];
}
dif >>= 1;
j++;
}
x = xaux;
y = yaux;
int z = minim(c1, c2);
xaux = (x * A + y * B) % n + 1;
yaux = (y * C + z * D) % n + 1;
x = xaux;
y = yaux;
return z;
}
int main()
{
in >> n >> m >> p;
for(int i = 2; i <= n; i++)
{
in >> t[i] >> cost[i];
vf[++nvf] = i;
urm[nvf] = lst[t[i]];
lst[t[i]] = nvf;
}
in >> X >> Y >> A >> B >> C >> D;
euler(1);
for(int i = 2; i < 2 * N; i++)
lg[i] = 1 + lg[i >> 1];
for(int i = 1; i <= ne; i++)
r[i][0] = e[i];
for(int j = 1; j <= lg[ne]; j++)
for(int i = 1; i <= ne; i++)
if(i + (1 << (j - 1)) <= ne)
r[i][j] = minim(r[i][j - 1], r[i + (1 << (j - 1))][j - 1]);
for(int i = 2; i <= n; i++)
{
str[i][0] = t[i];
coststr[i][0] = cost[i];
}
for(int j = 1; j <= lg[n]; j++)
for(int i = 1; i <= n; i++)
{
str[i][j] = str[str[i][j - 1]][j - 1];
coststr[i][j] = minim2(coststr[i][j - 1], coststr[str[i][j - 1]][j - 1]);
}
while(m--)
{
int z = drumMinim(X, Y);
if(m < p)
out << z << '\n';
}
return 0;
}