Cod sursa(job #592214)

Utilizator rudarelLup Ionut rudarel Data 27 mai 2011 07:45:49
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>
#include <vector>
#define Nmax 32002
#define pb push_back
#define mp make_pair
#define Ct 19
#define INF 2147000000
 
using namespace std;
 
vector< pair<int,int> > v[Nmax];
int Niv[Nmax];
int Str[Ct][Nmax],Min[Ct][Nmax];
int n,m,P,nmax,Z;
 
inline int Minim(int x,int y){ return x<y ? x:y; }
inline int Maxim(int x,int y){ return x>y ? x:y; }
 
inline void dfs(int x,int niv){
    vector< pair<int,int> >::iterator it;
    Niv[x]=niv;
    if( niv> nmax ) nmax=niv;
     
    for(it=v[x].begin(); it!=v[x].end(); ++it)
        if( ! Niv[it->first] ){
            Str[0][it->first]=x;
            Min[0][it->first]=it->second;
            dfs(it->first,niv+1);
        }
}
 
inline void afla(int x,int y){
    int px,py,p,aux;
    if( Niv[x] < Niv[y] ) aux=x, x=y, y=aux;
    for(px=0; (1<<px) <= Niv[x]; ++px); --px;
    for(py=0; (1<<py) <= Niv[y]; ++py); --py;
     
    for(p=px; p>=0; --p)
        if( Niv[x]-(1<<p) >= Niv[y] )
            Z=Minim(Z,Min[p][x]),x=Str[p][x];
     
    for(p=py; p>=0; --p)
        if( Str[p][x] != Str[p][y] ){
            Z=Minim(Z,Min[p][x]); x=Str[p][x];
            Z=Minim(Z,Min[p][y]); y=Str[p][y];
        }
    if( x != y ){
        Z=Minim(Z,Min[0][x]);
        Z=Minim(Z,Min[0][y]);
    }
}
 
int main(){
    int X,Y,A,B,C,D,i,j,x,y,p;
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    scanf("%d%d%d",&n,&m,&P);
    for(i=2;i<=n;++i){
        scanf("%d%d",&x,&y);
        v[i].pb(mp(x,y));
        v[x].pb(mp(i,y));
    }
    scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
     
    dfs(1,1); --nmax;
    for(p=0; (1<<p)<=nmax; ) ++p; --p;
    for(i=1;i<=p;++i)
        for(j=1;j<=n;++j){
            Str[i][j]=Str[i-1][Str[i-1][j]];
            Min[i][j]=Minim(Min[i-1][Str[i-1][j]], Min[i-1][j]);
        }
     
    for(i=1;i<=m;++i){
        Z=INF;
        if( X==Y ) Z=0;
        else afla(X,Y);
         
        if( i>= m-P+1 )printf("%d\n",Z);
         
        X=( X*A + Y*B ) % n +1;
        Y=( Y*C + Z*D ) % n +1;
        //scanf("%d%d",&X,&Y);
    }
     
    fclose(stdin); fclose(stdout);
    return 0;
}