Pagini recente » Cod sursa (job #2196618) | Cod sursa (job #3184448) | Cod sursa (job #1325488) | Cod sursa (job #2155154) | Cod sursa (job #1738914)
#include <fstream>
#include <vector>
#define DIM 66000
#define INF 1000000000
using namespace std;
int D[17][DIM]; //D[i][j] cea mai mica muchie considerand deasupra nodului j 2^i muchii
int S[17][DIM];
int niv[DIM];
vector<pair<int, int> > L[DIM];
pair<int, int> t[DIM];
int n, m, p, a, b, c, d, x, y, z, u, v;
void dfs(int nod, int nv) {
niv[nod] = nv;
for (int i=0;i<L[nod].size(); i++) {
int vec = L[nod][i].first;
int cost = L[nod][i].second;
if (niv[ vec ] == 0) {
t[vec] = make_pair( nod, cost );
dfs(vec, nv+1);
}
}
}
int main () {
ifstream fin ("atac.in");
ofstream fout("atac.out");
fin>>n>>m>>p;
for (int i=2;i<=n;i++) {
fin>>u>>v;
L[i].push_back(make_pair(u,v));
L[u].push_back(make_pair(i,v));
}
fin>>x>>y>>a>>b>>c>>d;
dfs(1, 1);
for (int i=0;i<=16;i++)
S[i][1] = D[i][1] = INF;
for (int i=2;i<=n;i++) {
D[0][i] = t[i].second;
S[0][i] = t[i].first;
}
for (int log=1; log <=16; log++)
for (int i=2;i<=n;i++) {
if ((1 << log) <= niv[i]) { // S[log][i] = al 2^log stramos al lui i
S[log][i] = S[ log-1 ][ S[ log-1 ][i] ];
D[log][i] = min(D[log-1][i], D[log-1][ S[log-1][i] ]);
} else {
D[log][i] = INF;
S[log][i] = INF;
}
}
for (int pas = m; pas--;) {
// muchia minima pe drumul de la x la y
int log = 16;
int f = x;
int g = y;
int z = INF;
while (niv[f] != niv[g]) {
if (niv[f] > niv[g]) {
if (S[log][f] != INF && niv[ S[log][f] ] >= niv[g]) {
z = min(z, D[log][f]);
f = S[log][f];
}
} else {
if (S[log][g] != INF && niv[ S[log][g] ] >= niv[f]) {
z = min(z, D[log][g]);
g = S[log][g];
}
}
log--;
}
if (f != g) {
log = 16;
while (S[0][f] != S[0][g]) {
if (S[log][f] != S[log][g]) {
z = min(z, D[log][f]);
z = min(z, D[log][g]);
f = S[log][f];
g = S[log][g];
}
log --;
}
z = min(z, D[0][f]);
z = min(z, D[0][g]);
}
if (pas < p)
fout<<(z != INF ? z : 0)<<"\n";
int x1 = (x*a + y*b) % n + 1;
int y1 = (y*c + z*d) % n + 1;
x = x1;
y = y1;
}
return 0;
}