Pagini recente » Cod sursa (job #2614509) | Cod sursa (job #714194) | Cod sursa (job #506) | Cod sursa (job #747687) | Cod sursa (job #2614665)
#include <bits/stdc++.h>
std::ifstream fin ("atac.in");
std::ofstream fout ("atac.out");
std::vector < std::pair < int, int > > edge[32005];
int parent[16][32005];
int rmq[16][32005];
int level[32005];
bool visited[32005];
void findParents (int node){
visited[node] = true;
for (int i=0; i<edge[node].size(); i++){
int next = edge[node][i].first;
if (visited[next] == false){
level[next ] = level[node] + 1;
parent[0][next] = node;
rmq[0][next] = edge[node][i].second;
for (int j=1; parent[j-1][parent[j-1][next]] != 0; j++){
parent[j][next] = parent[j-1][parent[j-1][next]];
rmq[j][next] = std::min (rmq[j-1][next], rmq[j-1][parent[j-1][next]]);
}
findParents (next);
}
}
}
int main(){
int V, E, Q, P, root=1, src, dest, i, cost;
fin >> V >> Q >> P;
E = V - 1;
for (i=2; i<=E+1; i++){
fin >> src >> cost;
dest = i;
edge[src].push_back ({dest, cost});
edge[dest].push_back ({dest, cost});
}
level[root] = 1;
findParents (root);
/*
for (i=1; i<=V; i++)
fout << rmq[1][i] << '\n';
*/
int node1, node2, A, B, C, D;
std::vector < int > ans;
fin >> node1 >> node2 >> A >> B >> C >> D;
while (Q--){
int answer;
if (node1 == node2)
answer = 0;
else{
int level1 = level[node1];
int level2 = level[node2];
int crt1 = node1;
int crt2 = node2;
if (level1 > level2){
std::swap (level1, level2);
std::swap (crt1, crt2);
}
int min = 1e9;
int p = 15, diff = level2 - level1;
while (level1 < level2){
if ((1 << p) <= diff){
diff -= (1 << p);
min = std::min (min, rmq[p][crt2]);
level2 -= (1 << p);
crt2 = parent[p][crt2];
}
p --;
}
p = 15;
int level = level1;
while (parent[0][crt1] != parent[0][crt2]){
if ((1 << p) < level and parent[p][crt1] != parent[p][crt2]){
min = std::min (min, rmq[p][crt1]);
min = std::min (min, rmq[p][crt2]);
crt1 = parent[p][crt1];
crt2 = parent[p][crt2];
level -= (1 << p);
}
p --;
}
min = std::min (min, std::min (rmq[0][crt1], rmq[0][crt2]));
answer = min;
}
ans.push_back (answer);
node1 = (node1 * A + node2 * B) % V + 1;
node2 = (node2 * C + answer * D) % V + 1;
}
for (i=ans.size()-P; i<ans.size(); i++)
fout << ans[i] << '\n';
return 0;
}