Pagini recente » Cod sursa (job #467936) | Cod sursa (job #1225603) | Cod sursa (job #1505130) | Cod sursa (job #1588627) | Cod sursa (job #1254908)
#include<fstream>
#include<vector>
#define N 32100
#define M 17
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int n,m,sol,P,dif,l,i,j,lc,x,y,k,a,b,c,d,e[N * 2],logg[N * 2],niv[N * 2],nivnod[N],p[N],cost[M][N],t[M][N],rmq[M + 1][N * 2];
vector<int>v[N];
inline void dfs(int x,int nivel){
e[++k] = x;
niv[k] = nivel;
nivnod[x] = nivel;
p[x] = k;
for(vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
{
dfs(*it, nivel + 1);
e[++k] = x;
niv[k] = nivel;
}
}
inline void RMQ(){
for(i = 2; i <= k; ++i)
logg[i] = logg[i >> 1] + 1;
for(i = 1; i <= k; ++i)
rmq[0][i] = i;
for(i = 1; (1 << i) <= k; ++i)
for(j = 1; j + (1 << (i - 1)) <= k; ++j)
{
rmq[i][j] = rmq[i - 1][j];
if(niv[rmq[i - 1][j + (1 << (i - 1))]] < niv[rmq[i][j]])
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
for(i = 1; (1 << i) <= n; ++i)
for(j = 1; j <= n; ++j)
t[i][j] = t[i - 1][t[i - 1][j]],
cost[i][j] = min(cost[i - 1][j], cost[i - 1][t[i - 1][j]]);
}
inline int LCA(int x,int y){
x = p[x];
y = p[y];
if(x > y)
swap(x, y);
int dif,l,sol,poz;
dif = y - x + 1;
l = logg[dif];
poz = dif - (1 << l);
sol = rmq[l][x];
if(niv[sol] > niv[rmq[l][x + poz]])
sol = rmq[l][x + poz];
return e[sol];
}
inline int rez(int x,int tata){
dif = nivnod[x] - nivnod[tata];
l = logg[dif];
int rez = INF;
for(int i = 0; i <= l; ++i)
if(dif & (1 << i))
{
rez = min(rez, cost[i][x]);
x = t[i][x];
}
return rez;
}
int main()
{
f >> n >> m >> P;
for(i = 2; i <= n; ++i)
{
f >> x >> y;
v[x].push_back(i);
cost[0][i] = y;
t[0][i] = x;
}
dfs(1, 0);
RMQ();
f >> x >> y >> a >> b >> c >> d;
for(i = 1; i <= m; ++i)
{
lc = LCA(x, y);
sol = min(rez(x, lc), rez(y, lc));
if(x == y)
sol = 0;
if(i > m - P)
g << sol << '\n';
x = (1LL * x * a + 1LL * y * b) % n + 1;
y = (1LL * y * c + 1LL * sol * d) % n + 1;
}
return 0;
}