Pagini recente » Cod sursa (job #2590858) | Cod sursa (job #910325) | Cod sursa (job #2313458) | Cod sursa (job #1708617) | Cod sursa (job #1099376)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 33009;
const int INF = (1 << 30);
int N; int M; int P; int X; int Y; int A; int B; int C; int D;
bool see[2 * NMAX];int lg[NMAX * 2];int H[20][2 * NMAX];int C_min[20][2 * NMAX];
int Euler[NMAX * 2];int min_ind;int Level[2 * NMAX]; int Level_nod[2 * NMAX];int rmq[20][NMAX * 2];
int T[NMAX * 2];
vector<pair <int, int> > G[NMAX];
int F[NMAX];
void read() {
fin >> N >> M >> P;
for(int i = 2; i <= N; ++i) {
int u, v;
fin >> u >> v;
G[i].push_back(make_pair(u, v));
G[u].push_back(make_pair(i, v));
}
fin >> X >> Y >> A >> B >> C >> D;
}
void dfs(int nod, int level) {
Euler[++Euler[0]] = nod;
Level[Euler[0]] = level;
Level_nod[nod] = level;
F[nod] = Euler[0];
for(unsigned i = 0 ;i < G[nod].size(); ++i) {
if(F[G[nod][i].first]) continue;
H[0][G[nod][i].first] = nod;
C_min[0][G[nod][i].first] = G[nod][i].second;
dfs(G[nod][i].first, level + 1);
Euler[++Euler[0]] = nod;
Level[Euler[0]] = level;
}
}
void rmq_arbore() {
for(int i = 2; i <= Euler[0]; ++i)
lg[i] = lg[i/2] + 1;
for(int i = 1; i <= Euler[0]; ++i)
rmq[0][i] = i;
for(int i = 1; (1 << i) <= Euler[0]; ++i)
for(int j = 1; j <= Euler[0] - (1 << i) + 1; ++j) {
rmq[i][j] = rmq[i - 1][j];
if(Level[rmq[i][j]] > Level[rmq[i - 1][j + (1 << (i - 1))]])
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
for(int i = 1; (1 << i) <= N; ++i)
for(int j = 1; j <= N; ++j) {
H[i][j] = H[i - 1][H[i - 1][j]];
C_min[i][j] = C_min[i - 1][j];
if(C_min[i][j] > C_min[i - 1][H[i - 1][j]])
C_min[i][j] = C_min[i - 1][H[i - 1][j]];
}
}
int query(int X, int Y) {
if(X == Y) return 0;
int st = F[X]; int dr = F[Y]; if(st > dr) swap(st, dr);
int dif = dr - st + 1;
int lgg = lg[dif];
int l1 = 1 << lgg;
int sh = dif - l1;
int sol = rmq[lgg][st];
if(Level[sol] > Level[rmq[lgg][dr - l1 + 1]])
sol = rmq[lgg][dr - l1 + 1];
int LCA = Euler[sol];
// fout << LCA <<'\n';
int min_cost = (1<<30);
int arr[] = {X, Y};
for(int i = 0 ;i < 2; ++i){
int x = arr[i];
int d = Level_nod[x] - Level_nod[LCA];
while(d > 0) {
int l = lg[d];
min_cost = min(min_cost, C_min[l][x]);
x = H[l][x];
d -= (1 << l);
}
}
return min_cost;
}
int main() {
read();
dfs(1, 0);
rmq_arbore();
int LCA;
int Z; int min_cost;
for(int i = 1; i <= M; ++i) {
min_cost = query(X, Y);
if(i >= M - P)
fout << min_cost <<'\n';
X = (X * A + Y * B) % N + 1;
Y = (Y * C + min_cost * D) % N + 1;
}
return 0;
}