Pagini recente » Cod sursa (job #34777) | Cod sursa (job #9067) | Cod sursa (job #66307) | Cod sursa (job #59650) | Cod sursa (job #3131238)
#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], bl[21][NMAX + 1], poz[NMAX + 1], lg2[2 * NMAX + 1], h, ne;
int cost[21][NMAX + 1];
bool viz[NMAX + 1];
void dfs(int x){
e[++ne] = x;
poz[x] = ne;
viz[x] = 1;
h = max(h, nivel[x]);
for(auto y : g[x]){
if(viz[y.first] == 1)
continue;
nivel[y.first] = 1 + nivel[x];
bl[0][y.first] = x;
cost[0][y.first] = y.second;
dfs(y.first);
e[++ne] = x;
}
}
int lca(int x, int y){
int st = poz[x], dr = poz[y];
if(st > dr)
swap(st, dr);
int l = lg2[dr - st + 1];
int p = (1 << l);
x = r[l][st + p - 1];
y = r[l][dr];
if(nivel[x] > nivel[y])
x = y;
return x;
}
int descompunere(int x, int y){
int d = nivel[x] - nivel[t];
int ans = inf, p = 0;
while(d != 0){
if((d & (1 << p)) == 0){
p++;
continue;
}
ans = min(ans, cost[p][x]);
x = bl[p][x];
d -= (1 << p);
p++;
}
return ans;
}
int atac(int x, int y){
int t = lca(x, y);
int d = nivel[x] - nivel[t];
return min(descompunere(x, t), descompunere(y, t));
}
int main(){
int n = 0, m = 0, p = 0;
cin >> n >> m >> p;
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});
}
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];
}
}
/*
bl[i][j] = costul minim al muchiilor de la nodul j la stramosul de ordin 2^i
bl[i][j] = min(bl[i - 1][j], bl[i - 1][j']), unde j' = stramosul de ordin 2^(i - 1)
*/
for(int i = 1; (1 << i) <= h; i++){
for(int j = 1; j <= n; j++){
int jp = bl[i - 1][j];
bl[i][j] = min(bl[i - 1][j], bl[i - 1][jp]);
cost[i][j] = min(cost[i - 1][j], cost[i - 1][jp]);
if(cost[i][j] == 0)
cost[i][j] = inf;
}
}
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);
if(x == y)
z = 0;
if(i >= m - p){
cout << z << "\n";
}
x = (x * a + y * b) % n + 1;
y = (y * c + z * d) % n + 1;
}
return 0;
}