Pagini recente » Cod sursa (job #147730) | Cod sursa (job #1532880) | Cod sursa (job #149853) | Cod sursa (job #1797798) | Cod sursa (job #1211151)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define st first
#define nd second
using namespace std;
typedef long long int64;
ifstream in("atac.in");
ofstream out("atac.out");
const int NMAX = 32010, LOG2NMAX = 16, inf = 0x3f3f3f3f;
int N, P, M, X, Y, A, B, C, D;
int euler[2 * NMAX], RMQ[2 * NMAX][LOG2NMAX], first[NMAX], level[2 * NMAX], ancestor[LOG2NMAX][NMAX], node_level[NMAX], father[NMAX], cost[NMAX], best[LOG2NMAX][NMAX];
bool visited[NMAX];
vector<pair<int, int> > G[NMAX];
void DF(const int node, const int lvl) {
visited[node] = true;
euler[++euler[0]] = node;
level[++level[0]] = lvl;
first[node] = euler[0];
node_level[node] = lvl;
for (size_t it = 0; it < G[node].size(); ++it) {
if (visited[G[node][it].st]) continue;
father[G[node][it].st] = node;
cost[G[node][it].st] = G[node][it].nd;
DF(G[node][it].st, lvl + 1);
euler[++euler[0]] = node;
level[++level[0]] = lvl;
}
}
void Compute_RMQ() {
int i, j;
for (i = 1; i <= euler[0]; ++i) RMQ[i][0] = i;
for (i = 1; (1 << i) <= euler[0]; ++i)
for (j = 1; j + (1 << i) - 1 <= euler[0]; ++j)
if (level[RMQ[j][i - 1]] < level[RMQ[j + (1 << (i - 1))][i - 1]]) RMQ[j][i] = RMQ[j][i - 1];
else RMQ[j][i] = RMQ[j + (1 << (i - 1))][i - 1];
}
#undef st
#undef nd
int LCA(int st, int nd) {
st = first[st], nd = first[nd];
if (st > nd) swap(st, nd);
int lg2 = -1, value;
for (value = nd - st + 1; value; value >>= 1, ++lg2);
if (level[RMQ[st][lg2]] < level[RMQ[nd - (1 << lg2) + 1][lg2]])
return euler[RMQ[st][lg2]];
return euler[RMQ[nd - (1 << lg2) + 1][lg2]];
}
#define st first
#define nd second
void Build_ancestor() {
int i, j;
for (i = 1; i <= N; ++i) ancestor[0][i] = father[i], best[0][i] = cost[i];
for (i = 1; (1 << i) < N; ++i)
for (j = 1; j <= N; ++j) {
ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
best[i][j] = min(best[i - 1][j], best[i - 1][ancestor[i - 1][j]]);
}
}
int main() {
int i, j, cost;
in >> N >> P >> M;
for (i = 2; i <= N; ++i) {
in >> j >> cost;
G[i].push_back(make_pair(j, cost));
G[j].push_back(make_pair(i, cost));
}
DF(1, 0);
Compute_RMQ();
Build_ancestor();
cerr << LCA(3, 7);
in >> X >> Y >> A >> B >> C >> D;
for (i = 1; i <= P; ++i) {
int res = inf, node = LCA(X, Y), value = node_level[X] - node_level[node], go = X;
for (int bit = 0; value && bit < (node_level[X] - node_level[node]); ++bit)
if ((1 << bit) & value) {
res = min(res, best[bit][go]);
go = ancestor[bit][go];
value -= (1 << bit);
}
value = node_level[Y] - node_level[node], go = Y;
for (int bit = 0; value && bit < (node_level[Y] - node_level[node]); ++bit)
if ((1 << bit) & value) {
res = min(res, best[bit][go]);
go = ancestor[bit][go];
value -= (1 << bit);
}
if (i > P - M) out << res << '\n';
int _X = (X * A + Y * B) % N + 1;
int _Y = (Y * C + res * D) % N + 1;
X = _X, Y = _Y;
}
in.close(), out.close();
return 0;
}