Pagini recente » Cod sursa (job #1075974) | Cod sursa (job #254420) | Cod sursa (job #1277920) | 00001 | Cod sursa (job #1348867)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
typedef int var;
ifstream fin("atac.in");
ofstream fout("atac.out");
const var MAXN = 240002;
struct Edge {
var n, c;
Edge(var x, var y) {
n = x;
c = y;
}
};
vector<Edge> A[MAXN];
vector<var> EULER, DEPTH;
var B[MAXN], D[MAXN], PARENT[32][MAXN], MIN[32][MAXN];
var n, k, p;
var LOG[MAXN];
void euler(var node) {
for(vector<Edge>::iterator it = A[node].begin(); it != A[node].end(); ++it) {
Edge &e = *it;
if(e.n == PARENT[0][node]) continue;
PARENT[0][e.n] = node;
MIN[0][e.n] = e.c;
D[e.n] = D[node] + 1;
euler(e.n);
}
}
void build_min_table() {
for(var i=1; (1<<i)<=n; i++) {
for(var j=1; j<=n; j++) {
PARENT[i][j] = PARENT[i-1][PARENT[i-1][j]];
MIN[i][j] = min(MIN[i-1][j], MIN[i-1][PARENT[i-1][j]]);
}
}
}
inline var zeros(var d) {
return d & (-d);
}
var lca(var node1, var node2) {
var &d1 = D[node1], &d2 = D[node2];
var delta = d2-d1;
var minn = 1000001;
if(node1 == node2) return 0;
while(delta>0) {
var t = LOG[zeros(delta)];
delta -= zeros(delta);
minn = min(minn, MIN[t][node2]);
node2 = PARENT[t][node2];
}
delta = d1-d2;
while(delta>0) {
var t = LOG[zeros(delta)];
delta -= zeros(delta);
minn = min(minn, MIN[t][node1]);
node1 = PARENT[t][node1];
}
if(node1 == node2) return minn;
for(var i=LOG[D[node1]]; i>=0; i--) {
if(PARENT[i][node1] && PARENT[i][node1] != PARENT[i][node2]) {
minn = min(minn, MIN[i][node1]);
minn = min(minn, MIN[i][node2]);
node1 = PARENT[i][node1];
node2 = PARENT[i][node2];
}
}
minn = min(minn, MIN[0][node1]);
minn = min(minn, MIN[0][node2]);
return minn;
}
var build_log_table(var maxx) {
for(var i=2; i<=maxx; i++) {
LOG[i] = LOG[i/2] + 1;
}
}
int main() {
var t, c;
fin>>n>>k>>p;
for(var i=2; i<=n; i++) {
fin>>t>>c;
A[t].push_back(Edge(i, c));
A[i].push_back(Edge(t, c));
//EDGES.push_back(FullEdge(i, t, c));
}
euler(1);
build_min_table();
build_log_table(n+1);
var x, y, a, b, d;
fin>>x>>y>>a>>b>>c>>d;
for(var i=1; i<=k; i++) {
var rez = lca(x, y);
x = (x*a + y*b)%n + 1;
y = (y*c + rez*d)%n + 1;
if(i > k-p) {
fout<<rez<<'\n';
}
}
return 0;
}