Cod sursa(job #212408)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 5 octombrie 2008 13:17:51
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <vector>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
const int NMAX=32001;
int N,M,P,X,Y,Z,A,B,C,D,nr;
int s[32][NMAX];//s[j][[i]=al 2^j -lea stramos al lui i
int m[32][NMAX];//m[j][i]=minimul pe drumul de la i la al 2^j stramos al lui i
int rmq[33][2*NMAX],v[2*NMAX],log[2*NMAX];
int niv[NMAX],poz[NMAX];
vector< pair<int,int> > G[NMAX];
ifstream f("atac.in");
ofstream g("atac.out");
int min(int x,int y){
    return x<y?x:y;
    }
void read(){
     int i,u,v;
     f>>N>>M>>P;
     for (i=2;i<=N;++i){
         f>>u>>v;
         G[u].pb(mp(i,v));
         G[i].pb(mp(u,v));}
     f>>X>>Y>>A>>B>>C>>D;
     }
bool viz[NMAX];
void euler(int vf){
     vector< pair<int,int> >::iterator it;
     viz[vf]=true;
     v[++nr]=vf;
     poz[vf]=nr;
     for (it=G[vf].begin();it!=G[vf].end();++it)
       if (!viz[it->ff]){
            niv[it->ff]=niv[vf]+1;    
            s[0][it->ff]=vf;
            m[0][it->ff]=it->ss;      
            euler(it->ff);
            v[++nr]=vf;
            }
     }    
int lca(int x,int y){
     int i,j,w,k,ii,jj;
     i=poz[x];
     j=poz[y];
     if (i>j)  w=i,i=j,j=w;
     w=log[j-i+1];
     ii=rmq[w][i];
     jj=rmq[w][j-(1<<w)+1];
     if (niv[ii]<niv[jj]) k=ii;
       else k=jj;
     return k;
     }  
int drum(int x,int y){
     int i,k=niv[x]-niv[y],w=1000000;
     for (i=0;i<32;++i)
      if ((1<<i)&k){
       w=min(w,m[i][x]);
       x=s[i][x];}
     return w;
     }     
void solve(){
     int i,j,x,y;
     
     euler(1);
     for (i=2;i<=nr;++i) log[i]=log[i>>1]+1;
     for (i=1;i<=nr;++i) rmq[0][i]=v[i];
     for (i=1;i<=log[nr];++i)
       for (j=1;j<=nr-(1<<i)+1;++j){
          x=rmq[i-1][j];
          y=rmq[i-1][j+(1<<(i-1))];
          if (niv[x]<niv[y]) rmq[i][j]=x;
                  else rmq[i][j]=y;
          }
          
     for (i=1;i<32;++i)
       for (j=1;j<=N;++j){
         s[i][j]=s[i-1][s[i-1][j]];
         m[i][j]=min(m[i-1][j],m[i-1][s[i-1][j]]);
         }
     
     for (i=1;i<=M;++i){
        if (X==Y) Z=0;
        else{
        j=lca(X,Y);
        Z=min(drum(X,j),drum(Y,j));
            }
        x=1+(X*A+Y*B)%N;
        y=1+(Y*C+Z*D)%N;
        X=x;Y=y;
        if (i<M-P+1) continue;
        g<<Z<<'\n';}             
     }
int main(){
    read();
    solve();
    return 0;
}