Pagini recente » Cod sursa (job #2330331) | Cod sursa (job #2149063) | Rating Bach Minh Chau (Minh1) | Istoria paginii runda/hoata-pls2/clasament | Cod sursa (job #1135664)
//Problem atac from Infoarena
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define mp make_pair
const int INF = 1 << 30;
const int MAX_N = 32100;
const int MAX_LOG = 17;
int N, M, P;
vector<pair<int, int>> graph[MAX_N];
bool visited[MAX_N];
int X, Y, Z, A, B, C, D;
int euler_node[4 * MAX_N];
int euler_depth[4 * MAX_N];
int euler_pos[MAX_N];
int num_euler;
int max_depth;
int rm[MAX_LOG][4 * MAX_N];
int lg2[4 * MAX_N];
int ancestor[MAX_LOG][MAX_N];
int min_up[MAX_LOG][MAX_N];
void read_input();
void solve();
void dfs(int node, int depth);
void cross_euler(int node, int depth);
void build_rm();
void build_ancestry();
int rmq(int a, int b);
int lca(int a, int b);
int query(int node, int anc);
int mod(long long n, int MOD);
int main() {
read_input();
solve();
return 0;
}
void read_input() {
fin >> N >> M >> P;
for (int i = 2, x, c; i <= N; i += 1) {
fin >> x >> c;
graph[x].push_back(mp(i, c));
graph[i].push_back(mp(x, c));
}
fin >> X >> Y >> A >> B >> C >> D;
}
void solve() {
for (int l = 0; (1 << l) <= N; l += 1) {
for (int i = 1; i <= N; i += 1) {
min_up[l][i] = INF;
}
}
num_euler = 0;
max_depth = 0;
dfs(1, 1);
build_rm();
build_ancestry();
for (int i = 1; i <= M; i += 1) {
int w = lca(X, Y);
Z = (X == Y ? 0 : min(query(X, w), query(Y, w)));
if (i > M - P)
fout << Z << '\n';
X = mod(1LL * A * X + B * Y, N) + 1;
Y = mod(1LL * C * Y + D * Z, N) + 1;
}
}
void dfs(int node, int depth) {
visited[node] = true;
max_depth = max(max_depth, depth);
cross_euler(node, depth);
for (auto next: graph[node]) {
if (not visited[next.first]) {
ancestor[0][next.first] = node;
min_up[0][next.first] = next.second;
dfs(next.first, depth + 1);
cross_euler(node, depth);
}
}
}
inline void cross_euler(int node, int depth) {
num_euler += 1;
euler_pos[node] = num_euler;
euler_node[num_euler] = node;
euler_depth[num_euler] = depth;
rm[0][num_euler] = node;
}
void build_rm() {
lg2[1] = 0;
for (int i = 2; i <= num_euler; i += 1)
lg2[i] = lg2[i / 2] + 1;
for (int i = 1; i <= num_euler; i += 1) {
rm[0][i] = i;
}
for (int l = 1; (1 << l) <= num_euler; l += 1) {
for (int i = 1; i + (1 << l) - 1 <= num_euler; i += 1) {
rm[l][i] = rmq(rm[l - 1][i], rm[l - 1][i + (1 << (l - 1))]);
}
}
}
inline int rmq(int a, int b) {
if (euler_depth[a] < euler_depth[b]) {
return a;
} else {
return b;
}
}
inline int lca(int a, int b) {
a = euler_pos[a];
b = euler_pos[b];
if (a > b) swap(a, b);
int l = lg2[b - a + 1];
return euler_node[rmq(rm[l][a], rm[l][b - (1 << l) + 1])];
}
void build_ancestry() {
for (int l = 1; (1 << l) <= max_depth; l += 1) {
for (int i = 1; i <= N; i += 1) {
ancestor[l][i] = ancestor[l - 1][ancestor[l - 1][i]];
min_up[l][i] = min(min_up[l - 1][i], min_up[l - 1][ancestor[l - 1][i]]);
}
}
}
int query(int node, int anc) {
int da = euler_depth[euler_pos[anc]];
int dn = euler_depth[euler_pos[node]];
if (dn <= da) return INF;
int l = lg2[da - dn + 1];
return min(min_up[l][node], query(ancestor[l][node], anc));
}
inline int mod(long long n, int MOD) {
if (n < MOD) return n;
if (n < 2 * MOD) return n - MOD;
return n % MOD;
}