Cod sursa(job #1146848)

Utilizator alecsandrualex cuturela alecsandru Data 19 martie 2014 12:43:56
Problema Atac Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N=32100;
int parcurgere[20][2*N],lim,j,nr,n,m,poz[N],nou[N],vechi[N],nivel[N],d[16][N],bombe[16][N],cnt,u,p;
vector <int> vecini[200100];
void dfs(int tata,int k)
{
    int i,fiu;
    if(nou[tata]==0)
    {
        nou[tata]=++cnt;
        vechi[cnt]=tata;
        nivel[tata]=k;
    }
    parcurgere[1][++nr]=nou[tata];
    poz[nou[tata]]=nr;
    for(i=0;i<(int)vecini[tata].size();i++)
    {
        fiu=vecini[tata][i];
        dfs(fiu,k+1);
        parcurgere[1][++nr]=nou[tata];
    }
}
int main()
{
    int x,i,k,y;
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    scanf("%d%d%d",&n,&m,&u);
    for(i=2;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        d[0][i]=x;
        bombe[0][i]=y;
        vecini[x].push_back(i);
    }
    dfs(1,1);
    parcurgere[1][0]=nr;
    i=2;
    for(k=2;i<=nr;k++)
    {
        lim=parcurgere[k-1][0]-i/2;
        for(j=1;j<=lim;j++)
        {
            parcurgere[k][j]=min(parcurgere[k-1][j],parcurgere[k-1][j+i/2]);
           // printf("%d ",parcurgere[k][j]);
        }
        parcurgere[k][0]=lim;
       // printf("\n");
        i=1<<k;
    }
    for(i=1;i<=lim;i++)
    {
        parcurgere[k][i]=1;
    }
    lim=log2(n)+1;
    for(i=1;i<=lim;i++)
        for(j=1;j<=n;j++)
        {
            d[i][j]=d[i-1][d[i-1][j]];
            bombe[i][j]=min(bombe[i-1][j],bombe[i-1][d[i-1][j]]);
        }
    int a,b,rez,p1,p2,p3,p4,nx,ny,tx,xx,yy,rezf;
    scanf("%d%d%d%d%d%d",&x,&y,&p1,&p2,&p3,&p4);
    for(i=1;i<=m;i++)
    {
        a=nou[x];
        b=nou[y];
        if(a!=b)
        {
            xx=min(poz[a],poz[b]);
            yy=max(poz[a],poz[b]);
            lim=yy-xx-1;
            lim=log2(lim);
            p=1<<lim;
            rez=min(parcurgere[lim+1][xx],parcurgere[lim+1][yy-p]);
        }
        else
            rez=a;
        nx=nivel[x];
        ny=nivel[y];

        nr=nx-nivel[vechi[rez]];
        tx=x;
        rezf=2000000000;
        cnt=0;

        while(nr!=0)
        {
            if(nr%2!=0)
            {
                rezf=min(bombe[cnt][tx],rezf);
                tx=d[cnt][tx];
            }
            cnt++;
            nr/=2;
        }

        nr=ny-nivel[vechi[rez]];
        tx=y;
        cnt=0;

        while(nr!=0)
        {
            if(nr%2!=0)
            {
                rezf=min(bombe[cnt][tx],rezf);
                tx=d[cnt][tx];
            }
            cnt++;
            nr/=2;
        }
        if(i>m-u)
            printf("%d\n",rezf);
        x=(x*p1+y*p2)%n+1;
        y=(y*p3+rezf*p4)%n+1;
    }
    return 0;
}