Pagini recente » Cod sursa (job #2967056) | Cod sursa (job #2362898) | Cod sursa (job #2362976) | Istoria paginii utilizator/petrica81 | Cod sursa (job #974491)
Cod sursa(job #974491)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define newn a[x][i].second
#define cost a[x][i].first;
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int N = 32010;
const int E = N * 2;
const int L = 17;
int n, m, p, nr, A, B, C, D, X, Y, Z, t[L][N], dp[L][N],
first[N], euler[E], height[E], lg[E], rmq[L][E];
typedef pair <int, int> nod;
vector <nod> a[N];
void dfs(int x, int level)
{
++nr;
euler[nr] = x;
height[nr] = level;
first[x] = nr;
for(unsigned i=0; i<a[x].size(); i++)
{
dfs(newn, level+1);
++nr;
euler[nr] = x;
height[nr] = level;
}
}
void Rmq()
{
for(int i=2; i<=nr; i++)
lg[i] = lg[i>>1] + 1;
for(int i=1; i<=nr; i++)
rmq[0][i] = i;
for(int i=1; (1<<i) <= nr; i++)
for(int j=1; j <= nr - (1<<i); j++)
{
const int l = 1 << (i-1);
rmq[i][j] = rmq[i-1][j];
if(height[rmq[i][j]] > height[rmq[i-1][j+l]])
rmq[i][j] = rmq[i-1][j+l];
}
}
int LCA(int x, int y)
{
x = first[x], y = first[y];
if(x > y) swap(x, y);
const int l = lg[y-x+1];
int poz = rmq[l][x];
if(height[poz] > height[rmq[l][y-(1<<l)+1]])
poz = rmq[l][y-(1<<l)+1];
return poz;
}
void Ancestor()
{
for(int i=1; (1<<i) <= n; i++)
for(int j=1; j<=n; j++)
{
t[i][j] = t[i-1][t[i-1][j]];
dp[i][j] = min(dp[i-1][j], dp[i-1][t[i-1][j]]);
}
}
int Compute(int nod, int lca)
{
int rez = (1 << 25);
int depth = height[first[nod]] - height[first[lca]];
while(depth)
{
rez = min(rez, dp[lg[depth]][nod]);
nod = t[lg[depth]][nod];
depth -= (1 << lg[depth]);
}
return rez;
}
int Query(int x, int y)
{
if(x == y) return 0;
int lca = euler[LCA(X, Y)];
int drum1 = Compute(x, lca);
int drum2 = Compute(y, lca);
return min(drum1, drum2);
}
int main()
{
fin>>n>>m>>p;
for(int i=2; i<=n; i++)
{
fin>>t[0][i]>>dp[0][i];
a[t[0][i]].push_back(nod(dp[0][i], i));
}
fin>>X>>Y>>A>>B>>C>>D;
dfs(1, 0);
Rmq();
Ancestor();
while(m--)
{
Z = Query(X, Y);
X = (X*A + Y*B) % n + 1;
Y = (Y*C + Z*D) % n + 1;
if(m < p) fout<<Z<<'\n';
}
return 0;
}