Pagini recente » Borderou de evaluare (job #2912231) | Borderou de evaluare (job #2912232) | Borderou de evaluare (job #2912227) | Borderou de evaluare (job #2912225) | Cod sursa (job #3131203)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int NMAX = 32e3;
const int inf = 2e9;
vector <pair <int, int>> g[NMAX + 1];
int e[2 * NMAX + 1], nivel[NMAX + 1], r[21][2 * NMAX + 1], poz[NMAX + 1], lg2[NMAX + 1], ne;
int cost[NMAX + 1];
bool viz[NMAX + 1];
void dfs(int x){
e[++ne] = x;
poz[x] = ne;
viz[x] = 1;
for(auto y : g[x]){
if(viz[y.first] == 1)
continue;
nivel[y.first] = 1 + nivel[x];
dfs(y.first);
e[++ne] = x;
cost[x] = min(cost[x], y.second);
}
}
int lca(int x, int y){
int st = poz[x], dr = poz[y]; // secvența din vectorul e
if(st > dr)
swap(st, dr);
int l = lg2[dr - st + 1]; // similar rmq clasic
int p = (1 << l); // similar rmq clasic
x = r[l][st + p - 1];
y = r[l][dr];
if(nivel[x] > nivel[y]) // comparăm nodurile de nivel minim din fiecare secvență
x = y;
return x;
}
int atac(int x, int y){
return cost[lca(x, y)];
}
int main(){
int n = 0, m = 0, p = 0;
cin >> n >> m >> p;
cost[1] = inf;
for(int i = 2; i <= n; i++){
int x = 0, c = 0;
cin >> x >> c;
g[x].push_back({i, c});
g[i].push_back({x, c});
cost[i] = inf;
}
dfs(1);
lg2[0] = -1;
for(int i = 1; i <= ne; i++){
lg2[i] = 1 + lg2[i >> 1];
r[0][i] = e[i];
}
for(int i = 1; (1 << i) <= ne; i++){
for(int j = (1 << i); j <= ne; j++){
r[i][j] = r[i - 1][j];
int p = (1 << (i - 1));
if(nivel[r[i - 1][j - p]] < nivel[r[i - 1][j]])
r[i][j] = r[i - 1][j - p];
}
}
int x = 0, y = 0, a = 0, b = 0, c = 0, d = 0;
cin >> x >> y >> a >> b >> c >> d;
for(int i = 0; i < m; i++){
int z = atac(x, y);
//cout << "perechea este " << x << " " << y << "\n";
if(i >= m - p){
cout << z << "\n";
}
x = (x * a + y * b) % n + 1;
y = (y * c + z * d) % n + 1;
}
return 0;
}