Cod sursa(job #285)

Utilizator sarabogdanSara Nicolae Bogdan sarabogdan Data 8 decembrie 2006 17:24:09
Problema Atac Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.66 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int euler[200001];
int adancimi[200001];
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 ;
int m , p;
int a[32000][100], ind;
long opt[1000][1000];
int stiva[33001];
int stramosi[33000][16];
int coststr[33000][16];
int k ;
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++;
     }
   //  kk = www&(www^(www-1));
     if (doi[kk]>b-a+1)
        kk--;
  //   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);    
    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;
        minim = 200000;
        if (X!=1&& X != var && X != Y)
        {
        aux = X;
        if (cost[aux] < minim)
           minim = cost[aux];
        
        while(tata[aux]!=var && tata[aux]!=0)
        {
                             if (cost[aux]<minim)
                                minim = cost[aux];
                             aux = tata[aux];
                            
        }
        if (cost[aux]<minim)
                                minim = cost[aux];
        }
        if (Y!=1 && Y != var && X!=Y)
        {
        aux = Y;
        if (cost[aux] < minim)
           minim = cost[aux];
        
        while(tata[aux]!=var&&tata[aux]!=0)
        {
                             if (cost[aux]<minim)
                                minim = cost[aux];
                             aux = tata[aux];
                            
        }
        if (cost[aux]<minim)
                                minim = cost[aux];
        }
        if (minim==200000)
           minim = 0;
     //   printf("%d %ld\n",X,Y);
        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;   
    }
//    printf("%d ",lca(poz[352],poz[307]));
    return 0;
}