Pagini recente » Cod sursa (job #1023991) | Cod sursa (job #2801750) | Cod sursa (job #2876284) | Cod sursa (job #762094) | Cod sursa (job #795157)
Cod sursa(job #795157)
#include <fstream>
#include <vector>
using namespace std;
const int N = 32005, LG = 15, inf = 0x3f3f3f3f;
int T[LG][N], C[LG][N], doi[2 * N], depth[N], n;
ifstream in("atac.in");
ofstream out("atac.out");
struct Muchie{
int y, c;
Muchie(){
c = 0;
}
Muchie(int _y, int _c){
y = _y;
c = _c;
}
};
vector<Muchie> graph[N];
struct LowestCommonAncestor{
int rmq[1 + LG][2 * N], euler[2 * N], start[N], n, size;
vector<Muchie>* graph;
inline void sch(int& a, int& b){
int c = a;
a = b;
b = c;
}
inline int best(int x, int y){
return depth[x] < depth[y] ? x : y;
}
void dfs(int x){
rmq[0][++size] = x;
start[x] = size;
for (vector<Muchie> :: iterator it = graph[x].begin() ; it != graph[x].end() ; it++){
depth[it -> y] = 1 + depth[x];
T[0][it -> y] = x;
C[0][it -> y] = it -> c;
dfs(it -> y);
rmq[0][++size] = x;
}
}
void compute(){
size = 0;
dfs(1);
for (int i = 1 ; i <= LG ; i++)
for (int j = 1 ; j <= size ; j++)
rmq[i][j] = best(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1) )]);
for (int i = 1, j = 0 ; i <= size ; i <<= 1, j++)
doi[i] = j;
for (int i = 1 ; i <= size ; i++)
if (!doi[i])
doi[i] = doi[i - 1];
}
inline void assign_tree(vector<Muchie>* tree, int _n){
graph = tree;
n = _n;
compute();
}
inline int lca(int x, int y){
x = start[x]; y = start[y];
if (x > y)
sch(x, y);
int L = doi[y - x + 1];
return best(rmq[L][x], rmq[L][y - (1 << L) + 1]);
}
} LCA;
inline int min(int a, int b){
return a < b ? a : b;
}
void compute(){
LCA.assign_tree(graph, n);
for (int i = 1 ; i < LG ; i++)
for (int j = 1 ; j <= n ; j++){
T[i][j] = T[i - 1][ T[i - 1][j] ];
C[i][j] = T[i][j] ? min(C[i - 1][j], C[i - 1][ T[i - 1][j] ]) : inf;
}
}
inline int bomb(int x, int L){
int rez = inf;
for (int i = doi[L] ; i >= 0 ; i--)
if (L >= (1 << i)){
rez = min(rez, C[i][x]);
L -= 1 << i;
x = T[i][x];
}
return rez;
}
int solve(int x, int y){
int L = depth[LCA.lca(x, y)];
return min(bomb(x, depth[x] - L), bomb(y, depth[y] - L));
}
int main(){
int m, p, r, x, y, A, B, C, D;
in >> n >> m >> p;
for (int i = 2 ; i <= n ; i++){
in >> x >> y;
graph[x].push_back(Muchie(i, y));
}
compute();
in >> x >> y >> A >> B >> C >> D;
while (m--){
r = solve(x, y);
if (m < p)
out << r << "\n";
x = (A * x + B * y) % n + 1;
y = (C * y + D * r) % n + 1;
}
return 0;
}