Pagini recente » Cod sursa (job #12604) | Cod sursa (job #2127304) | Cod sursa (job #2927226) | Cod sursa (job #3236190) | Cod sursa (job #3142152)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 32001;
const int LOG = 20;
int upmin[NMAX][LOG], depth[NMAX];
vector<int> children[NMAX];
int up[NMAX][LOG];
int n, m, p, x, y;
int a, b, c, d;
void dfs(int s) {
for(auto u : children[s]) {
depth[u] = depth[s]+1;
up[u][0] = s;
for(int j=1; j<LOG; j++) {
up[u][j] = up[up[u][j-1]][j-1];
upmin[u][j] = min(upmin[u][j-1], upmin[up[u][j-1]][j-1]);
}
dfs(u);
}
}
int lca(int x, int y) {
if(x==y)
return 0;
int minbomb = 1e9;
if(depth[x] < depth[y])
swap(x, y);
int k = depth[x] - depth[y];
for(int j=LOG-1; j>=0; j--)
if(k & (1<<j)) {
if(x != y)
minbomb = min(minbomb, upmin[x][j]);
x = up[x][j];
}
if(x == y)
return minbomb;
for(int j=LOG-1; j>=0; j--)
if(up[x][j] != up[y][j]) {
minbomb = min(minbomb, upmin[x][j]);
minbomb = min(minbomb, upmin[y][j]);
x = up[x][j];
y = up[y][j];
}
return min(minbomb, min(upmin[x][0], upmin[y][0]));
}
int main()
{
fin >> n >> m >> p;
for(int i=2; i<=n; i++) {
int x, y;
fin >> x >> y;
children[min(i, x)].push_back(max(i, x));
upmin[i][0]=y;
}
for(int j=0; j<LOG; j++) {
upmin[1][j]=1e9;
up[1][j]=1;
}
fin >> x >> y >> a >> b >> c >> d;
dfs(1);
while(m--) {
int minbomb = lca(x, y);
x=(x*a+y*b)%n+1;
y=(y*c+minbomb*d)%n+1;
if(m<p)
fout << minbomb << '\n';
}
return 0;
}