Pagini recente » Cod sursa (job #863135) | Cod sursa (job #494285) | Cod sursa (job #545622) | Cod sursa (job #280611) | Cod sursa (job #1491075)
#include <fstream>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
const int INF = 1 << 30;
int M[17][32300], Str[17][32300],cost[16][32001], h[32001],v[120000], euler[120000], d[120000],depth[32001], N, R, P, o = 0, min1 = 120000,MD=0;
vector<pair<int, int>> g[36002];
void e(int current, int& i, int dist){
euler[i] = current;
d[i] = dist;
depth[current] = dist;
if (MD < dist) MD = dist;
if (h[current] == -1)h[current] = i;
for (auto& j : g[current]){
Str[0][j.second] = current;
cost[0][j.second] = j.first;
++i;
e(j.second, i, dist + 1);
++i;
euler[i] = current;
d[i] = dist;
}
}
void rmq(){
for (int i = 0; i <= o; ++i) M[0][i] = i;
for (int j = 1; 1 << j <= o;++j)
for (int i = 0; i + (1 << j) - 1 < o; ++i)
if (d[M[j - 1][i]] < d[M[j - 1][i + (1 << (j - 1))]])
M[j][i] = M[j - 1][i];
else M[j][i] = M[j - 1][i + (1 << (j - 1))];
}
int Lca(int a, int b){
int p1 = h[a], p2 = h[b];
if (p2 < p1){
p1 ^= p2; p2 ^= p1; p1 ^= p2;
}
int k = 0, p = 1;
while (p <= p2 - p1 + 1){ p <<= 1; ++k; }
--k;
p >>= 1;
return euler[d[M[k][p1]] <= d[M[k][p2 - (1 << k) + 1]] ? M[k][p1] : M[k][p2 - (1 << k) + 1]];
}
void BA() {
for (int l = 1; (1 << l) <= MD; l += 1) {
for (int i = 1; i <= N; i += 1) {
Str[l][i] = Str[l - 1][Str[l - 1][i]];
if (cost[l - 1][i]<cost[l - 1][Str[l - 1][i]])
cost[l][i] = cost[l - 1][i];
else cost[l][i] = cost[l - 1][Str[l - 1][i]];
}
}
}
int min2(int node, int anc) {
int result = INF;
for (int l = depth[node] - depth[anc]; l > 0; l -= (1 << v[l])) {
result = result < cost[v[l]][node] ? result : cost[v[l]][node];
node = Str[v[l]][node];
}
return result;
}
int main(){
ifstream f("atac.in");
ofstream of("atac.out");
int a, b,c,D,X,Y;
f >> N >> R >> P;
for (int i = 2; i <= N; ++i){
f >> a >> b;
g[a].push_back(make_pair(b , i));
}
f >> X >> Y >> a >> b >> c >> D;
memset(h, -1, sizeof(h));
for (int j = 0; (1 << j) <= N; ++j) {
for (int i = 1; i <= N; ++i) {
cost[j][i] = INF;
}
}
e(1,o,1);
rmq();
for (int i = 2; i <= o; ++i)
v[i] = 1 + v[i / 2];
BA(); int LC, m1, m2;
for (int i = 1; i <= R; ++i){
if (X == Y) min1 = 0;
else{
LC = Lca(X, Y), m1 = min2(X, LC), m2 = min2(Y, LC);
min1 = m1 < m2 ? m1 : m2;
}
if (R - P < i){
of <<min1 << "\n";
}
X = (X*a + Y*b) % N + 1;
Y = (Y*c + D*min1) % N + 1;
}
}