Pagini recente » Cod sursa (job #1364109) | Cod sursa (job #2891199) | Cod sursa (job #2318404) | Cod sursa (job #521263) | Cod sursa (job #1558628)
#include<fstream>
#include<vector>
#include<iostream>
#include<iterator>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
vector <pair <int, int> > G[40000];
int TT[20][40000], Dist[20][40000], Level[40000], Use[40000], Log[40000], Sol[500005];
int n, m, p, a, b, c, d, x, y, dist, k;
int const oo = 10000000;
void citire()
{
int i;
f>>n>>m>>p;
for(i=2; i<=n; i++){
f>>x>>c;
G[i].push_back(make_pair(x, c));
G[x].push_back(make_pair(i, c));
}
f>>x>>y>>a>>b>>c>>d;
}
void DFSL(int nod)
{
Use[nod] = 1;
int vecin, cost, i;
vector < pair <int, int> > :: iterator it;
for(it = G[nod].begin(); it != G[nod].end(); it++){
vecin = it -> first;
cost = it -> second;
if(!Use[vecin]){
Level[vecin] = Level[nod] + 1;
TT[0][vecin] = nod;
Dist[0][vecin] = cost;
DFSL(vecin);
}
}
}
void precalc()
{
DFSL(1);
int i, j;
for(i=2; i<=n; i++)
Log[i] = Log[i/2] + 1;
for(i=1; i<=Log[n]; i++)
for(j=1; j<=n; j++){
TT[i][j] = TT[i-1][TT[i-1][j]];
Dist[i][j] = min(Dist[i-1][TT[i-1][j]], Dist[i-1][j]);
}
}
void ance(int & nod, int p)
{
int red;
while(p){
red = Log[p];
dist = min(dist, Dist[red][nod]);
nod = TT[red][nod];
p -= (1<<red);
}
}
int rez()
{
int diff, i, x1, y1;
while(m--){
x1 = x;
y1 = y;
dist = oo;
if(Level[x] < Level[y])
swap(x, y);
diff = Level[x] - Level[y];
ance(x, diff);
for(i = Log[Level[x]]; i >= 0; i--)
if(TT[i][x] != TT[i][y]){
dist = min(dist, min(Dist[i][x], Dist[i][y]));
x = TT[i][x];
y = TT[i][y];
}
if(x != y){
dist = min(dist, min(Dist[0][x], Dist[0][y]));
}
if(dist == oo)
dist = 0;
Sol[++k] = dist;
x = (x1*a + y1*b)%n + 1;
y = (y1*c + dist*d)%n + 1;
}
for(i = k - p + 1; i<=k; i++)
g<<Sol[i]<<" ";
g<<"\n";
}
int main()
{
citire();
precalc();
rez();
return 0;
}