Pagini recente » Cod sursa (job #3362058) | Cod sursa (job #3361480) | Cod sursa (job #3357704) | Diferente pentru template/algoritmiada-2015/header intre reviziile 2 si 3 | Cod sursa (job #3361891)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 32000, LOGMAX = 16, VALMAX = 1000000000;
struct node
{
int depth;
bool isRoot = true;
vector<int> children;
};
node tree[NMAX + 5];
int n,m,p,x,y,A,B,C,D;
int up[NMAX + 5][LOGMAX + 5];
int rmq[NMAX + 5][LOGMAX + 5];
int root;
void dfs(int node, int dt)
{
tree[node].depth = dt;
for(int i = 0; i < tree[node].children.size(); ++i){
dfs(tree[node].children[i], dt + 1);
}
}
int minEdge(int x, int y)
{
int ans = VALMAX;
if(x == y){
return 0;
}
if(tree[x].depth < tree[y].depth){
swap(x, y);
}
int levelDiff = tree[x].depth - tree[y].depth;
for(int i = LOGMAX; i >= 0; --i){
if(levelDiff & (1 << i)){
ans = min(ans, rmq[x][i]);
x = up[x][i];
}
}
if(x == y){
return ans;
}
for(int i = LOGMAX; i >= 0; --i){
if(up[x][i] != up[y][i]){
ans = min(ans, rmq[x][i]);
ans = min(ans, rmq[y][i]);
x = up[x][i];
y = up[y][i];
}
}
return min(ans, min(rmq[x][0], rmq[y][0]));
}
int main()
{
fin >> n >> m >> p;
for(int i = 2; i <= n; ++i){
int node, val;
fin >> node >> val;
tree[i].isRoot = false;
up[i][0] = node;
rmq[i][0] = val;
tree[node].children.push_back(i);
}
for(int j = 1; j <= LOGMAX; ++j){
for(int i = 1; i <= n; ++i){
rmq[i][j] = VALMAX;
}
}
for(int j = 1; j <= LOGMAX; ++j){
for(int i = 1; i <= n; ++i){
up[i][j] = up[up[i][j - 1]][j - 1];
rmq[i][j] = min(rmq[i][j - 1], rmq[up[i][j - 1]][j - 1]);
}
}
for(int i = 1; i <= n; ++i){
if(tree[i].isRoot){
root = i;
break;
}
}
dfs(root, 0);
fin >> x >> y >> A >> B >> C >> D;
for(int i = 0; i < m; ++i){
int z = minEdge(x, y);
if(m - i <= p){
fout << z << '\n';
}
x = (1ll * x * A + 1ll * y * B) % n + 1;
y = (1ll * y * C + 1ll * z * D) % n + 1;
}
return 0;
}