Cod sursa(job #61)

Utilizator sarabogdanSara Nicolae Bogdan sarabogdan Data 4 decembrie 2006 20:16:05
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.31 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int euler[200001];
int adancimi[300001];
int poz[200001];
int min[200000][25];
int minpos[200000][25];
int cost[32001];
int tata[32001];
int bif[33000];
int n , i , j , x , y , q , nr;
int m , p;
int a[32000][100], ind;
int biti[101];
int bit;

int stiva[33001];
int stramosi[23][32001];
int coststr[23][32001];
int k , logn ;
int aux , eu;
int kk;
int X,Y,A,B,C,D,Z , var , minim;
long doi[20];
struct xy
{
       int x , y;
};
xy sir[32001];
int www;
int lca(int a , int b)
{
     kk = 0;
     www = b - a + 1;
     
     while(www)
     {
               www>>=1;
               kk++;
     }
  
     if (doi[kk]>b-a+1)
        kk--;
    
     k = doi[kk];
   
     if ( min[a][kk] <= min[b-k+1][kk])
        return euler[minpos[a][kk]];
     else
        return euler[minpos[b-k+1][kk]];
}   
void df(int nod) 
{
     bif[nod] = 1;
     stiva[0]++;
     stiva[stiva[0]] = nod;  
     eu++;
     euler[eu] = stiva[stiva[0]];
     adancimi[eu] = stiva[0];
    
     ind = 0;
     for (int q = 1 ; q <= a[nod][0];q++)
     {
         if (bif[a[nod][q]]==0)
         {
                               ind = 1;
                               bif[a[nod][q]] = 1;
                               tata[a[nod][q]] = nod;
                               df(a[nod][q]);
         }
     }
     if (ind==0)
     {
        stiva[0]--;
        eu++;
        euler[eu] = stiva[stiva[0]];
        adancimi[eu] = stiva[0];
        
     }           
}
int main()
{
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    doi[0] = 1;
    doi[1]=2;doi[2]=4;doi[3]=8;doi[4]=16;doi[5]=32;doi[6]=64;doi[7]=128;doi[8]=256;doi[9]=512;doi[10]=1024;doi[11]=2048;doi[12]=4096;doi[13]=8192;doi[14]=16384;doi[15]=32768;doi[16]=65536;doi[17]=131072;doi[18]=262144;
    scanf("%d%d%d",&n,&m,&p);
    
    for (i = 1 ; i < n ; i++)
    {
        scanf("%d %d",&sir[i].x,&sir[i].y);
        a[sir[i].x][0]++;
        a[sir[i].x][a[sir[i].x][0]] = i+1;
        a[i+1][0]++;
        a[i+1][a[i+1][0]] = sir[i].x;
    }
    df(1);
    for (i = 1 ; i < n ; i++)
    {
        if (tata[i+1]==sir[i].x)
           cost[i+1] = sir[i].y;
         if (tata[sir[i].x]==i+1)
            cost[sir[i].x] = i+1;     
    }
    for (i = 1 ; i < eu ; i++)
        poz[euler[i]] = i;
 
    aux = eu;
    while(aux)
    {
              k++;
              aux>>=1;
    }
    if (doi[k] > eu)
       k--;

    for (i = 1 ; i < eu ; i++)
    {
        min[i][0] = adancimi[i];
        minpos[i][0] = i;
    }
    for (i = 1 ; i <= k ; i++)
    {
        for (j = 1 ; j < eu ; j++)
        {
            
                     if (j+doi[i-1] < eu)
                     {
                     kk = doi[i-1];
                     if ( min[j][i-1] < min[j+kk][i-1])
                     {
                     min[j][i] = min[j][i-1];
                     minpos[j][i] = minpos[j][i-1];
                     }
                     else
                     {
                     min[j][i] = min[j+kk][i-1];
                     minpos[j][i] = minpos[j+kk][i-1];
                     }
                     }
                     
                     else
                     {
                     min[j][i] = min[j][i-1];
                     minpos[j][i] = minpos[j][i-1];
                     }
                     
        }
    } 
    scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);    
    tata[1] = 1;
 //   for (i = 1 ; i <= n ; i++)
 //       printf("%ld ",tata[i]);
        
    aux = n;
    logn = 0;
    while(aux)
    {
              aux/=2;
              logn++;
    }
    if(pow(2,logn)>n)
                     logn--;
        
    for (i = 1; i <= n ; i++)
        stramosi[0][i] = tata[i];
                     
    for (i = 1 ; i <= logn ; i++)
    {
        for (j = 1 ; j <= n ; j++)
            stramosi[i][j] = stramosi[i-1][stramosi[i-1][j]];
    }
    
    for (i = 1 ; i <= n ; i++)
        coststr[0][i] = cost[i];
            
    for (i = 1 ; i <= logn ; i++)
    {
        for (j = 1 ;j <= n ; j++)
        {
            if (adancimi[poz[j]]-1 < pow(2,i))
                                  coststr[i][j] = coststr[i-1][j];
            else
            {                  
            if (coststr[i-1][j] < coststr[i-1][stramosi[i-1][j]])
               coststr[i][j] = coststr[i-1][j];
            else
               coststr[i][j] = coststr[i-1][stramosi[i-1][j]];
            }
        }
    }    
  //  for (i = 1 ; i < eu ; i++)
 //       printf("%ld ",adancimi[i]);
 //   printf("\n"); 
//    printf("%ld ", adancimi[poz[978]]-adancimi[poz[358]]);
    for (i = 1 ; i <= m ; i++)
    {               
        if (poz[Y]>poz[X])
        var = lca(poz[X],poz[Y]);
        else
        var = lca(poz[Y],poz[X]);
        if (tata[X]==Y)
           var = Y;
        if (tata[Y]==X)
           var = X;
        if (X==1 || Y == 1)
           var = 1;
        k = abs(adancimi[poz[X]] - adancimi[poz[var]]);
       
        if ( X!=var)
        {
        kk = X;
        nr = 0;
        minim = 200000;
        biti[0] = 0;
        while (k)
        {
              biti[0]++;
              biti[biti[0]] = k %2;
              k/=2;
        }
     
        bit = biti[0];
        for (j = biti[0] ; j >= 1 ; j--)
        {
            if (biti[j]==1)
            {
                           if (coststr[bit-1][kk]<minim && coststr[bit-1][kk])
                           {
                                                        minim = coststr[bit-1][kk];
                                                        kk = stramosi[bit-1][kk];
                           }
            }
            bit--;
        }
            /*
        while(k)
        {
                if (k%2==1)
                {
                           if (coststr[nr][kk]<minim )
                           {
                                                     minim = coststr[nr][kk];
                                                     kk = stramosi[nr][kk];
                           }
                }
                k/=2;
                nr++;
        }
        */
        }
        if ( Y != var)
        {
        kk = Y;
        k = abs(adancimi[poz[Y]] - adancimi[poz[var]]);
        nr = 0;
        biti[0] = 0;
        while (k)
        {
              biti[0]++;
              biti[biti[0]] = k %2;
              k/=2;
        }
        bit = biti[0];
        for (j = biti[0] ; j >= 1 ; j--)
        {
            if (biti[j]==1)
            {
                           if (coststr[bit-1][kk]<minim && coststr[bit-1][kk])
                           {
                                                        minim = coststr[bit-1][kk];
                                                        kk = stramosi[bit-1][kk];
                           }
            }
            bit--;
        }
        /*
        while(k)
        {
                if (k%2==1)
                {
                           if (coststr[nr][kk]<minim )
                           {
                                                     minim = coststr[nr][kk];
                                                     kk = stramosi[nr][kk];
                           }
                }
                k/=2;
                nr++;
        }
        */
        }
        if (minim==200000)
           minim = 0;
  //      printf("%d %ld %ld %ld\n",X,Y,abs(adancimi[poz[X]] - adancimi[poz[var]]),var);
        if ( i >= m-p+1)
        {
             if (X==Y)
             {
                      minim = 0;
                      printf("%d\n",minim);
             }
             else
             if (tata[Y]==X)
             {
                minim = cost[Y];
                printf("%d\n",cost[Y]);
             }
             else   
             if (tata[X]==Y)
             {
                minim = cost[X];
                
                printf("%d\n",cost[X]);
             }    
             else     
             {
             
             printf("%d\n",minim);
             }
        }
                               
        
        
        X = (X*A + Y*B)%n+1;
        Y = (Y*C + minim*D)%n+1;   
    }
  
    return 0;
}