Pagini recente » Cod sursa (job #387445) | Cod sursa (job #2221776) | Cod sursa (job #202497) | Cod sursa (job #1006964) | Cod sursa (job #2092121)
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("atac.in");
ofstream out ("atac.out");
int rmq[26][32005],pt[26];
int level[32005],poz[32005],ap[32005],euler[320005];
pair<int,int>stramosi[26][32005];
bool hz[32005];
vector<pair<int,int> >v[32005];
int k,n,m,p,a,b,c,d,x,y,z,z1,z2,A,B,C,D,dx,ad,num,s1,s2,aux;
void dfs (int nod) {
int vecin;
rmq[0][++k] = nod;
poz[nod] = k;
hz[nod] = 1;
for (int i = 0; i < v[nod].size(); i ++) {
vecin = v[nod][i].first;
if (hz[vecin] == 0) {
level[vecin] = level[nod] + 1;
dfs (vecin);
rmq[0][++k] = nod;
}
}
rmq[0][++k] = nod;
}
int LCA (int x, int y) {
int a = max( poz[x] , poz[y]) - min (poz[x], poz[y]) + 1;
a = ap[a];
int b = min(poz[x], poz[y]);
int c = max (poz[x], poz[y]) - pt[a] + 1;
if (level[rmq[a][b]] < level[rmq[a][c]]) {
return rmq[a][b];
}
else {
return rmq[a][c];
}
}
void dfs_dinamica (int nod) {
hz[nod] = true;
int vecin,cost;
for (int i = 0; i < v[nod].size(); i ++) {
vecin = v[nod][i].first;
cost = v[nod][i].second;
if (hz[vecin] == false) {
stramosi[0][vecin].first = nod;
stramosi[0][vecin].second = cost;
dfs_dinamica (vecin);
}
}
}
int main (void) {
in >> n >> m >> p;
for (int i = 2; i <= n; i ++ ) {
in >> b >> c;
v[i].push_back (make_pair(b,c));
v[b].push_back (make_pair(i,c));
}
level[1] = 1;
dfs (1);
pt[0] = 1;
for (int i = 1; i <= 25; i ++) {
pt[i] = pt[i-1]*2;
}
for (int i = 2; i <= k; i ++) {
ap[i] = ap[i/2]+1;
}
for (int i = 1; i <= ap[k]; i ++) {
for (int j = 1; j <= k - pt[i-1]; j ++) {
if (level[rmq[i-1][j]] <= level[rmq[i-1][j+pt[i-1]]]) {
rmq[i][j] = rmq[i-1][j];
}
else {
rmq[i][j] = rmq[i-1][j+pt[i-1]];
}
}
}
for (int i = 1; i <= n; i ++) {
hz[i] = 0;
}
dfs_dinamica(1);
for (int i = 1; i <= ap[n]; i ++) {
for (int j = 1; j <= n; j ++) {
stramosi[i][j].first = stramosi[i-1][stramosi[i-1][j].first].first;
stramosi[i][j].second = min (stramosi[i-1][j].second, stramosi[i-1][stramosi[i-1][j].first].second);
}
}
in >> x >> y >> A >> B >> C >> D;
for (int i = 1; i <= m; i ++) {
a = x;
b = y;
c = LCA (x,y);
if ( a != c ){
dx = level[a] - level[c];
ad = ap[dx];
s1 = stramosi[ad][a].second;
dx -= pt[ad];
aux = ap[dx];
num = a;
while (dx) {
if (dx % 2 == 1) {
num = stramosi[aux][num].first;
}
dx /= 2;
aux --;
}
s2 =stramosi[ad][num].second;
z1 = min (s1,s2);
}
else {
z1 = 1e9;
}
if (b != c) {
dx = level[b] - level[c];
ad = ap[dx];
s1 = stramosi[ad][b].second;
dx -= pt[ad];
aux = ap[dx];
num = b;
while (dx) {
if (dx % 2 == 1) {
num = stramosi[aux][num].first;
}
dx /= 2;
aux --;
}
s2 =stramosi[ad][num].second;
z2 = min (s1,s2);
}
else{
z2 = 1e9;
}
z = min (z1,z2);
if (a==b) {
z = 0;
}
if (i >= m-p+1) {
out << z <<"\n";
}
x = (x*A + y*B) % n + 1;
y = (y*C + z*D) % n + 1;
}
return 0;
}