Pagini recente » Cod sursa (job #3121292) | Cod sursa (job #2064263) | Cod sursa (job #1858139) | Cod sursa (job #2415271) | Cod sursa (job #52991)
Cod sursa(job #52991)
#include <assert.h>
#include <stdio.h>
/*
* Naive LCA
*/
enum { maxn = 32001, inf = 0x3F3F3F3F };
struct ls
{
int n;
ls *next;
} *lst[maxn];
int n;
int dad[maxn];
int cost[maxn];
int lev[maxn];
int q[maxn], qs, qe;
int depth;
void add(int from, int to)
{
ls *p = new ls;
p->n = to;
p->next = lst[from];
lst[from] = p;
}
void bfs()
{
assert(qs < qe);
for(ls *p = lst[ q[qs] ]; p; p = p->next)
{
lev[p->n] = lev[ q[qs] ] + 1;
q[qe++] = p->n;
}
qs++;
}
void precalc()
{
qe = 1;
q[0] = 0;
dad[0] = -1;
while(qs != qe)
bfs();
assert(qe == n);
}
int lca(int a, int b)
{
if(lev[a] > lev[b])
{
int t = a;
a = b;
b = t;
}
assert(lev[a] <= lev[b]);
while(lev[a] != lev[b])
b = dad[b];
while(a != b)
{
assert(a != 0 && b != 0);
assert(lev[a] = lev[b]);
a = dad[a];
b = dad[b];
}
return a;
}
int calc(int a, int b)
{
int c = lca(a, b);
int i, ret = inf;
for(i = a; i != c; i = dad[i])
{
assert(i > 0 && i < n);
if(cost[i] < ret) ret = cost[i];
}
for(i = b; i != c; i = dad[i])
{
assert(i > 0 && i < n);
if(cost[i] < ret) ret = cost[i];
}
return ret;
}
int main()
{
int i, count, interested, start_printing;
int x, y, z, a, b, c, d;
FILE *f = fopen("atac.in", "r");
if(!f) return 1;
fscanf(f, "%d%d%d", &n, &count, &interested);
start_printing = count - interested;
for(i = 1; i < n; i++)
{
fscanf(f, "%d%d", &dad[i], &cost[i]);
dad[i]--;
add(dad[i], i);
}
fscanf(f, "%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
fclose(f);
f = fopen("atac.out", "w");
if(!f) return 1;
precalc();
for(i = 0; i < count; i++)
{
z = calc(x - 1, y - 1);
if(i >= start_printing)
fprintf(f, "%d\n", z);
x = (x * a + y * b) % n + 1;
y = (y * c + z * d) % n + 1;
}
fclose(f);
return 0;
}