Pagini recente » Cod sursa (job #458104) | Cod sursa (job #1050500) | Cod sursa (job #1511706) | Cod sursa (job #2739530) | Cod sursa (job #2436004)
// wish me luck
//Good luck to problems!
#include <bits/stdc++.h>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
const int NMAX = 32010;
const int LMAX = 20;
const int inf = 2e9;
vector < pair < int, int> > v[NMAX];
int n,m,p, X, Y, A, B, C, D, minim;
int k,euler[2 * NMAX], lvl[NMAX], pos[NMAX];
int lg[2 * NMAX], rmq[LMAX][2 * NMAX];
int dp[LMAX][NMAX], cost[LMAX][NMAX];
int eulvl[2 * NMAX];
void dfs(int nod, int level){
euler[++k] = nod;
eulvl[k] = level;
lvl[nod] = level;
pos[nod] = k;
for(auto it: v[nod])
if(!lvl[it.first]){
dp[0][it.first] = nod;
cost[0][it.first] = it.second;
dfs(it.first, level + 1);
euler[++k] = nod;
eulvl[k] = level;
}
}
void buildRMQ(){
int i,j;
for(i = 2 ; i <= k ; i++)
lg[i] = lg[i / 2] + 1;
for(i = 1 ; i <= k ; i++)
rmq[0][i] = euler[i];
for(i = 1 ; i <= lg[k] ; i++)
for(j = 1 ; j <= k - (1 << i) ; j++)
if(lvl[rmq[i - 1][j]] <= lvl[rmq[i - 1][j + (1 << (i - 1))]])
rmq[i][j] = rmq[i - 1][j];
else
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
int LCA(int x, int y){
x = pos[x];
y = pos[y];
if(x > y)
swap(x, y);
int dif = (y - x + 1);
int l = lg[dif];
if(lvl[rmq[l][x]] < lvl[rmq[l][y - (1 << l) + 1]])
return rmq[l][x];
return rmq[l][y - (1 << l) + 1];
}
void buildDP(){
int i,j;
for(i = 1 ; (1 << i) <= n ; i++)
for(j = 1 ; j <= n; j++){
dp[i][j] = dp[i - 1][dp[i -1][j]];
cost[i][j] = min(cost[i - 1][j], cost[i - 1][dp[i - 1][j]]);
}
}
int main(){
int i,x,y;
f >> n >> m >> p;
for(i = 2 ; i <= n ; i++){
f >> x >> y;
v[x].push_back(make_pair(i, y));
v[i].push_back(make_pair(x, y));
}
f >> X >> Y >> A >> B >> C >> D;
dfs(1,1 );
buildRMQ();
buildDP();
int common, cx, cy, difx, dify, up;
for( i = 1 ; i <= m ; i++){
//g << X << " " << Y << "\n";
if(X != Y){
common = lvl[LCA(X,Y)];
cx = X;
cy = Y;
difx = lvl[X] - common;
dify = lvl[Y] - common;
up = 0;
minim = inf;
while(difx > 0 && X > 0){
if(difx & 1){
minim = min(minim, cost[up][X]);
X = dp[up][X];
}
up++;
difx /= 2;
}
up = 0;
while(dify > 0 && Y > 0){
if(dify & 1){
minim = min(minim, cost[up][Y]);
Y = dp[up][Y];
}
up++;
dify /= 2;
}
if(minim == inf)
minim = 0;
X = cx;
Y = cy;
}else{
minim = 0;
}
if(i > m - p)
g << minim << "\n";
X = (X * A + Y * B) % n + 1;
Y = (Y * C + minim * D) % n + 1;
}
return 0;
}