Pagini recente » Cod sursa (job #1108281) | Monitorul de evaluare | Cod sursa (job #158098) | Cod sursa (job #1102022) | Cod sursa (job #2077915)
#include <fstream>
#include <vector>
#define ff first
#define ss second
#define INF 2e9
#define DIM 32002
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int n, m, p, a, b, c, D, putere, put[DIM], Niv[DIM], viz[DIM], x, y, val;
pair<int, int> d[20][DIM];
vector<pair<int, int> > arb[DIM];
void dfs(int nod, int niv){
viz[nod] = 1;
for(int i = 0; i < arb[nod].size(); ++ i){
pair<int, int> nodc = arb[nod][i];
if(!viz[nodc.ff]){
d[0][nodc.ff] = make_pair(nod, nodc.ss);
Niv[nodc.ff] = niv;
dfs(nodc.ff, niv + 1);
}
}
}
void pow(){
for(int i = 2; i <= n; ++ i)
put[i] = put[i / 2] + 1;
}
int lca(int x, int y){
if(Niv[y] < Niv[x])
swap(x, y);
int dif = Niv[y] - Niv[x];
while(dif){
putere = put[dif];
y = d[putere][y].ff;
dif -= (1 << putere);
}
if(x == y)
return x;
int ok = 1;
while(x && d[0][x].ff != d[0][y].ff){
if(ok == 1)
putere = put[Niv[x]];
else
-- putere;
ok = 0;
if(d[putere][x].ff != d[putere][y].ff){
x = d[putere][x].ff;
y = d[putere][y].ff;
ok = 1;
}
if(x == y)
return x;
}
return d[0][x].ff;
}
int sol(int x, int y){
if(x == y)
return INF;
if(Niv[y] < Niv[x])
swap(x, y);
int dif = Niv[y] - Niv[x];
int minim = INF;
while(dif){
int putere = put[dif];
minim = min(minim, d[putere][y].ss);
y = d[putere][y].ff;
dif -= (1 << putere);
}
return minim;
}
int main()
{
f>>n>>m>>p;
for(int i = 2; i <= n; ++ i){
f>>x>>y;
arb[i].push_back(make_pair(x, y));
arb[x].push_back(make_pair(i, x));
}
f>>x>>y>>a>>b>>c>>D;
dfs(1, 1);
pow();
for(int k = 1; (1 << k) <= n; ++ k)
for(int i = 1; i <= n; ++ i){
d[k][i].ff = d[k - 1][d[k - 1][i].ff].ff;
d[k][i].ss = min(d[k - 1][i].ss, d[k - 1][d[k - 1][i].ff].ss);
}
for(int cnt = 1; cnt <= m; ++ cnt){
int nod = lca(x, y);
val = min(sol(x, nod), sol(y, nod));
if(val == INF)
val = 0;
if(cnt >= m - p + 1)
g<<val<<'\n';
x = (x * a + y * b) % (n + 1);
y = (y * c + val * D) % (n + 1);
}
return 0;
}