Pagini recente » Cod sursa (job #62299) | Cod sursa (job #2695678) | Cod sursa (job #2494233) | Clasament temaichc | Cod sursa (job #2435773)
#include <bits/stdc++.h>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
const int NMAX = 32010;
const int LMAX = 20;
const int inf = 2e9;
vector < pair < int, int> > v[NMAX];
int n,m,p, X, Y, A, B, C, D, minim;
int k,euler[2 * NMAX], lvl[NMAX], pos[NMAX], father[NMAX], dist[NMAX], Dist[NMAX];
int lg[2 * NMAX], rmq[LMAX][2 * NMAX];
vector < pair < int, int > > ve[NMAX];
void dfs(int nod, int level){
euler[++k] = nod;
lvl[nod] = level;
pos[nod] = k;
for(auto it: v[nod])
if(!lvl[it.first]){
for(auto el: ve[nod]){
ve[it.first].push_back(make_pair(el.first, min(el.second, it.second)));
}
ve[it.first].push_back(make_pair(nod, it.second));
father[it.first] = nod;
dist[it.first] = it.second;
Dist[it.first] = Dist[nod] + it.second;
dfs(it.first, level + 1);
euler[++k] = nod;
}
}
void buildRMQ(){
int i,j;
for(i = 2 ; i <= k ; i++)
lg[i] = lg[i / 2] + 1;
for(i = 1 ; i <= k ; i++)
rmq[0][i] = euler[i];
for(i = 1 ; i <= lg[k] ; i++)
for(j = 1 ; j <= k - (1 << i) ; j++)
if(lvl[rmq[i - 1][j]] <= lvl[rmq[i - 1][j + (1 << (i - 1))]])
rmq[i][j] = rmq[i - 1][j];
else
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
int LCA(int x, int y){
x = pos[x];
y = pos[y];
if(x > y)
swap(x, y);
int dif = (y - x + 1);
int l = lg[dif];
if(lvl[rmq[l][x]] < lvl[rmq[l][y - (1 << l) + 1]])
return rmq[l][x];
return rmq[l][y - (1 << l) + 1];
}
void anotherDFS(int nod, int ancestor){
while(nod != ancestor){
minim = min(minim, dist[nod]);
nod = father[nod];
}
}
int main(){
int i,x,y;
f >> n >> m >> p;
for(i = 2 ; i <= n ; i++){
f >> x >> y;
v[x].push_back(make_pair(i, y));
}
f >> X >> Y >> A >> B >> C >> D;
dfs(1,1);
buildRMQ();
/*for(i = 1 ; i <= n ; i++){
for(auto it: ve[i])
g << "( " << it.first << "," << it.second << ") ";
g << "\n";
}
return 0;*/
int common;
for( i = 1 ; i <= m ; i++){
if(X != Y){
common = LCA(X, Y);
minim = 2e9;
for(auto it: ve[X])
if(it.first == common)
minim = min(minim, it.second);
for(auto it: ve[Y])
if(it.first == common)
minim = min(minim, it.second);
//anotherDFS(X, common);
//anotherDFS(Y, common);
}else{
minim = 0;
common = X;
}
if(i > m - p)
g << minim << "\n";
X = (X * A + Y * B) % n + 1;
Y = (Y * C + minim * D) % n + 1;
}
return 0;
}