Pagini recente » Cod sursa (job #69302) | Cod sursa (job #1801893) | Cod sursa (job #1885296) | Cod sursa (job #191836) | Cod sursa (job #1114360)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_N = 32005;
const int MAX_INT = 2147000000;
typedef pair<int, int> pere;
vector<pere> tree[MAX_N];
int min_on_chain[17][MAX_N];
int ancestor[17][MAX_N];
int level[MAX_N];
void dfs(int node, int father, int edge_cost) {
ancestor[0][node] = father;
level[node] = level[father] + 1;
min_on_chain[0][node] = edge_cost;
for(vector<pere> :: iterator it = tree[node].begin(); it != tree[node].end(); ++ it) {
if(it->first != father) {
dfs(it->first, node, it->second);
}
}
}
inline int get_lca(int x, int y) {
if(level[x] < level[y]) {
swap(x, y);
}
for(int pace = 15; pace >= 0; -- pace) {
if(level[ancestor[pace][x]] >= level[y]) {
x = ancestor[pace][x];
}
}
if(x == y) {
return x;
}
for(int pace = 15; pace >= 0; -- pace) {
if(ancestor[pace][x] != ancestor[pace][y]) {
x = ancestor[pace][x];
y = ancestor[pace][y];
}
}
return ancestor[0][x];
}
inline int solve_to_ancestor(int x, int y) {
int answer = MAX_INT;
for(int pace = 15; pace >= 0; -- pace) {
if(level[ancestor[pace][x]] >= level[y]) {
answer = min(answer, min_on_chain[pace][x]);
x = ancestor[pace][x];
}
}
return answer;
}
inline int solve(int x, int y) {
int lca = get_lca(x, y);
return min(solve_to_ancestor(x, lca), solve_to_ancestor(y, lca));
}
int main() {
ifstream fin("atac.in");
ofstream fout("atac.out");
int n, m, p;
fin >> n >> m >> p;
for(int i = 2; i <= n; ++ i) {
int x, cost;
fin >> x >> cost;
tree[x].push_back(pere(i, cost));
tree[i].push_back(pere(x, cost));
}
dfs(1, 0, MAX_INT);
for(int i = 1; (1 << i) <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
min_on_chain[i][j] = min(min_on_chain[i - 1][j], min_on_chain[i - 1][ancestor[i - 1][j]]);
}
}
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
for(int i = 1; i <= m; ++ i) {
int k = solve(x, y);
if(i >= m - p + 1) {
fout << k << "\n";
}
int new_x = (x * a + y * b) % n + 1;
int new_y = (y * c + k * d) % n + 1;
x = new_x;
y = new_y;
}
return 0;
}