Pagini recente » Cod sursa (job #2642208) | Profil Znupi | Cod sursa (job #1804123) | Cod sursa (job #960235) | Cod sursa (job #1964627)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 32000
#define NLOG 16
typedef struct ListNode
{
int value;
struct ListNode *next;
} ListNode;
ListNode* CreateListNode(int value)
{
ListNode *new_node = (ListNode*)malloc(sizeof(ListNode));
*new_node = (ListNode){value, NULL};
return new_node;
}
void AddToList(ListNode **list, int value)
{
ListNode *new_node = CreateListNode(value);
new_node->next = *list;
*list = new_node;
}
typedef struct Node
{
int exit;
ListNode *sons;
} Node;
int ancestors[NMAX + 1][NLOG];
int costs[NMAX + 1][NLOG];
Node tree[NMAX + 1];
int stack[NMAX + 1];
static inline int min(int a, int b) { return a < b ? a : b; }
void Swap(int *a, int *b)
{
int aux = *a;
*a = *b;
*b = aux;
}
void Precalc(int root, int nst)
{
static int time = 0;
int i;
stack[nst] = root;
if (nst > 1) {
int fa = ancestors[root][0];
for (i = 1; (1 << i) < nst; ++i) {
ancestors[root][i] = ancestors[fa][i - 1];
costs[root][i] = min(costs[root][i - 1], costs[fa][i - 1]);
fa = ancestors[fa][i - 1];
}
}
ListNode *it = tree[root].sons;
while (it != NULL) {
Precalc(it->value, nst + 1);
it = it->next;
}
tree[root].exit = ++time;
}
int Query(int x, int y)
{
if (x == y) {
return 0;
}
int res = (1 << 30);
while (x != y) {
if (tree[x].exit > tree[y].exit) {
Swap(&x, &y);
}
int ind = 0;
while (ind < NLOG && ancestors[x][ind] != 0) {
int fa = ancestors[x][ind];
if (tree[fa].exit <= tree[y].exit) {
++ind;
} else {
break;
}
}
if (ind > 0) {
--ind;
}
res = min(res, costs[x][ind]);
x = ancestors[x][ind];
}
return res;
}
int main()
{
FILE *fin = fopen("atac.in", "r");
FILE *fout = fopen("atac.out", "w");
int n, q, p, i, x, y, a, b, c, d;
fscanf(fin, "%d%d%d", &n, &q, &p);
for (i = 0; i <= n; ++i) {
tree[i].sons = NULL;
}
for (i = 2; i <= n; ++i) {
int fa, co;
fscanf(fin, "%d%d", &fa, &co);
ancestors[i][0] = fa;
costs[i][0] = co;
AddToList(&tree[fa].sons, i);
}
Precalc(1, 1);
fscanf(fin, "%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
for (i = 1; i <= q; ++i) {
int res = Query(x, y);
if (i > q - p) {
fprintf(fout, "%d\n", res);
}
int new_x = (x * a + y * b) % (n + 1);
int new_y = (y * c + res * d) % (n + 1);
x = new_x;
y = new_y;
}
return 0;
}