Cod sursa(job #1280124)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 1 decembrie 2014 14:43:55
Problema Atac Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <stdio.h>
#define INF 2000000000
#define MAXN 32000
#define LOGN 14
#define MAXK (2*MAXN-2)
#define MAXR (2*MAXN-1)
#define LOGR (LOGN+1)
int n, m, p, X, Y, a, b, c, d, k, r;
int cost[MAXK+1], val[MAXK+1], next[MAXK+1], lista[MAXN+1];
int first[MAXN+1], H[MAXR+1], niv[MAXR+1], lg[MAXR+1], rmq[LOGR+1][MAXK+1];
int str[LOGN+1][MAXN+1], hack[LOGN+1][MAXN+1];
inline int min2(int a, int b){
    if(a<=b){
        return a;
    }
    return b;
}
inline void adauga(int x, int y, int z){
    k++;
    cost[k]=z;
    val[k]=y;
    next[k]=lista[x];
    lista[x]=k;
}
inline void citire(){
    int i, x, y;
    FILE *fin;
    fin=fopen("atac.in", "r");
    fscanf(fin, "%d%d%d", &n, &m, &p);
    for(i=2; i<=n; i++){
        fscanf(fin, "%d%d", &x, &y);
        adauga(x, i, y);
    }
    fscanf(fin, "%d%d%d%d%d%d", &X, &Y, &a, &b, &c, &d);
    fclose(fin);
}
void euler(int x, int h){
    int p;
    r++;
    first[x]=r;
    H[r]=x;
    niv[r]=h;
    p=lista[x];
    while(p!=0){
        euler(val[p], h+1);
        r++;
        H[r]=x;
        niv[r]=h;
        p=next[p];
    }
}
inline void precalc_log(){
    int i;
    lg[1]=0;
    for(i=2; i<=r; i++){
        lg[i]=lg[i-1];
        if((1<<(lg[i]+1))==i){
            lg[i]++;
        }
    }
}
inline void precalc_rmq(){
    int i, j;
    for(i=1; i<=r; i++){
        rmq[0][i]=H[i];
    }
    for(j=1; j<=lg[r]; j++){
        for(i=(1<<j); i<=r; i++){
            rmq[j][i]=rmq[j-1][i];
            if(niv[first[rmq[j][i]]]>niv[first[rmq[j-1][i-(1<<(j-1))]]]){
                rmq[j][i]=rmq[j-1][i-(1<<(j-1))];
            }
        }
    }
}
inline void precalc_str(){
    int i, j, p;
    for(i=1; i<=n; i++){
        p=lista[i];
        while(p!=0){
            str[0][val[p]]=i;
            p=next[p];
        }
    }
    for(j=1; j<=lg[n]; j++){
        for(i=1; i<=n; i++){
            if(niv[first[i]]>(1<<j)){
                str[j][i]=str[j-1][str[j-1][i]];
            }
        }
    }
}
inline void precalc_hack(){
    int i, j, p;
    for(i=1; i<=n; i++){
        p=lista[i];
        while(p!=0){
            hack[0][val[p]]=cost[p];
            p=next[p];
        }
    }
    for(j=1; j<=lg[n]; j++){
        for(i=1; i<=n; i++){
            if(str[j][i]!=0){
                hack[j][i]=min2(hack[j-1][i], hack[j-1][str[j-1][i]]);
            }
        }
    }
}
inline int lca(int a, int b){
    int aux, l;
    a=first[a];
    b=first[b];
    if(a>b){
        aux=a;
        a=b;
        b=aux;
    }
    l=lg[b-a+1];
    aux=rmq[l][b];
    if(niv[first[aux]]>niv[first[rmq[l][a+(1<<l)-1]]]){
        aux=rmq[l][a+(1<<l)-1];
    }
    return aux;
}
inline int drum_direct(int a, int b){
    int nr, l;
    nr=INF;
    while(a!=b){
        l=lg[niv[first[b]]-niv[first[a]]];
        nr=min2(hack[l][b], nr);
        b=str[l][b];
    }
    return nr;
}
inline void query(){
    int i, e, z;
    FILE *fout;
    fout=fopen("atac.out", "w");
    for(i=1; i<=m; i++){
        e=lca(X, Y);
        z=(X!=Y)*min2(drum_direct(e, X), drum_direct(e, Y));
        if(i>=m-p+1){
            fprintf(fout, "%d\n", z);
        }
        X=(X*a+Y*b)%n+1;
        Y=(Y*c+z*d)%n+1;
    }
    fclose(fout);
}
int main(){
    citire();
    euler(1, 1);
    precalc_log();
    precalc_rmq();
    precalc_str();
    precalc_hack();
    query();
    return 0;
}