Pagini recente » Cod sursa (job #3222893) | Monitorul de evaluare | Cod sursa (job #2010019) | Cod sursa (job #573043) | Cod sursa (job #945087)
Cod sursa(job #945087)
#include<cmath>
#include<fstream>
#include<vector>
#include<algorithm>
#define VALOARE 900001
using namespace std;
const int knmax = 32005;
int lsb(int &x){
return x & -x;
}
int n, m, p, a, b, c, d, st, fin, val[knmax], dad[knmax];
vector<int> graph[knmax];
void read(){
ifstream in("atac.in");
in >> n >> m >> p;
val[1] = VALOARE;
for(int i = 2; i <= n; ++i){
in >> dad[i] >> val[i];
graph[dad[i]].push_back(i);
}
in >> st >> fin >> a >> b >> c >> d;
}
int lvl, level[knmax], p2[knmax * 2], anc[17][knmax], dp[17][knmax];
void dfs(int x){
level[x] = lvl;
++lvl;
for(int i = 0; i < graph[x].size(); ++i)
dfs(graph[x][i]);
--lvl;
}
void precomp(){
dfs(1);
p2[0] = -1;
for(int i = 1; i <= knmax * 2; ++i)
p2[i] = p2[i >> 1] + 1;
for(int i = 1; i <= n; ++i){
anc[0][i] = dad[i];
dp[0][i] = val[i];
}
for(int i = 1; i < 16; ++i)
for(int j = 1; j <= n; ++j){
dp[i][j] = min(dp[i - 1][j], dp[i - 1][anc[i - 1][j]]);
anc[i][j] = anc[i - 1][anc[i - 1][j]];
}
}
int ancestor(int x, int up){
up = fabs(up);
if(up == 0)
return x;
return ancestor(anc[p2[lsb(up)]][x], up - lsb(up));
}
int lca(int x, int y){
if(level[x] > level[y])
swap(x, y);
x = ancestor(x, level[y] - level[x]);
int left = 0, right = level[x], mid, last;
while(left <= right){
mid = (left + right) >> 1;
if(ancestor(x, mid) == ancestor(y, mid)){
last = mid;
right = mid - 1;
}
else
left = mid + 1;
}
return ancestor(x, last);
}
int way(int x, int up){
up = fabs(up);
if(up == 0)
return VALOARE;
return min(dp[p2[lsb(up)]][x], way(anc[p2[lsb(up)]][x], up - lsb(up)));
}
vector<int> ans;
void solve(){
precomp();
int t = m;
do{
--t;
if(st == fin)
ans.push_back(0);
else{
int mid = lca(st, fin);
int x = way(st, level[mid] - level[st]), y = way(fin, level[mid] - level[fin]);
ans.push_back(min(x, y));
}
st = ((long long)st * a + (long long)fin * b) % n + 1;
fin = ((long long)fin * c + (long long)ans.back() * d) % n + 1;
}while(t);
}
void write(){
ofstream out("atac.out");
for(int i = m - p; i < m; ++i)
out << ans[i] << "\n";
}
int main(){
read();
solve();
write();
return 0;
}