Pagini recente » Cod sursa (job #1543555) | Cod sursa (job #2222269) | Cod sursa (job #1804131) | Cod sursa (job #2314217) | Cod sursa (job #1491031)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
int M[15][32001], h[32001], euler[64002], v[64002], d[64002], N, R, P, o = 0, min1 = 100.000;
vector<pair<int, int>> g[36002], parrent[36002];
void e(int current, int& i, int dist){
euler[i] = current;
d[i] = dist;
if (h[current] == -1)h[current] = i;
for (auto& j : g[current]){
++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]];
}
int min2(int b, int c){
int rc = parrent[b][0].first;
while (b != c){
if (parrent[b][0].first < rc) rc = parrent[b][0].first;
b = parrent[b][0].second;
}
return rc;
}
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));
parrent[i].push_back(make_pair(b, a));
}
f >> X >> Y >> a >> b >> c >> D;
memset(h, -1, sizeof(h));
e(1,o,0);
rmq(); int k = 0;
for (int i = 1; i <= R; ++i){
++k;
int LC = Lca(X, Y), m1 = min2(X, LC), m2 = min2(Y, LC);
min1 = m1 < m2 ? m1 : m2;
if (R - k+1 <= P)
if (X == Y)of << "0\n";
else of << min1 << "\n";
X = (X*a + Y*b) % N + 1;
Y = (Y*c + D*min1) % N + 1;
}
}