Cod sursa(job #5656)

Utilizator filipbFilip Cristian Buruiana filipb Data 13 ianuarie 2007 17:21:53
Problema Atac Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <stdlib.h>
#define min(a, b) ((a < b) ? a : b)
#define INF 900000000
#define LG 16
#define NMax 32005
typedef struct lista { int id; struct lista *next; } lista;
typedef lista *Graf[NMax];

int N, M, P, S[LG][NMax], MN[LG][NMax], X, Y, lg[NMax], dep[NMax];
int X, Y, A, B, C, D;
Graf G;

void add_to_list(lista **l, int item)
{
     lista *tmp = (lista *)malloc(sizeof(lista));
     
     tmp->id = item;
     tmp->next = *l;
     *l = tmp;
}

void dfs(int nod)
{
     lista *f;
     int i;

     for (i = 1; i <= lg[dep[nod]]; i++)
         S[i][nod] = S[i-1][S[i-1][nod]],
         MN[i][nod] = min(MN[i-1][nod], MN[i-1][S[i-1][nod]]);
     
     for (f = G[nod]; f; f = f->next)
     { dep[f->id] = dep[nod] + 1; dfs(f->id); }

}

int query(int x, int y)
{
    int h, mn = INF;
    
    if (x == y) return 0;
    
    while (dep[x] > dep[y])
    {
          mn = min(mn, MN[lg[dep[x]-dep[y]]][x]);          
          x = S[lg[dep[x]-dep[y]]][x];
    }
    
    while (dep[y] > dep[x])
    {
          mn = min(mn, MN[lg[dep[y]-dep[x]]][y]);       
          y = S[lg[dep[y]-dep[x]]][y];
    }
    
    if (x == y) return mn;
              
    for (h = lg[dep[x]]; h >= 0; h--)
        if (S[h][x] != S[h][y])
           mn = min(min(mn, MN[h][x]), MN[h][y]),
           x = S[h][x], y = S[h][y];

    return min(min(mn, MN[0][x]), MN[0][y]);
} 

int main(void)
{
    int i, u, v, Xp, Yp, Z;
    
    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);
    
    scanf("%d %d %d", &N, &M, &P);
    for (i = 2; i < 32001; i++)
        lg[i] = lg[i/2] + 1;
    for (i = 1; i <= N; i++) G[i] = NULL;
    
    for (i = 2; i <= N; i++)
    {
        scanf("%d %d", &u, &v);
        add_to_list(&G[u], i);
        S[0][i] = u; MN[0][i] = v;        
    }
        
    dfs(1);
        
    scanf("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
        
    for (; M; M--)
    {                
        Z = query(X, Y);
             
        if (M <= P)
           printf("%d\n", Z);
                   
        Xp = (X * A + Y * B) % N + 1; Yp = (Y * C + Z * D) % N + 1;
        X = Xp; Y = Yp;
    }
        
    return 0;
}