Cod sursa(job #1146834)

Utilizator heracleRadu Muntean heracle Data 19 martie 2014 12:29:11
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <cstdio>
#include <vector>

const int Q=32006;

struct copil{
    int fiu,cost;
};

std::vector<copil> fiu[Q+1];

int n,q;

int tat[Q+1];

int euler[2*Q+16],ne,st[Q+1],nivel[Q+1];
int niv=0;
int r[18][2*Q+16] ,log[2*Q+16];

int m,p;


void make_tat()
{
    scanf("%d%d%d",&n,&m,&p);
    int a,b;
    for(int i=2; i<=n; i++)
    {
        scanf("%d%d",&a,&b);
        fiu[i].push_back( copil{a,b} );
        fiu[a].push_back( copil{i,b} );

    }

}


void dfs(int x,int tata)
{
    euler[++ne]=x;
    st[x]=ne;
    nivel[x]=niv;
    niv++;
    for(int i=0; i<fiu[x].size(); i++)
    {
        if(fiu[x][i].fiu==tata)
            continue;
        dfs(fiu[x][i].fiu,x);
        euler[++ne]=x;
    }
    niv--;
}

void make_lca()
{
    dfs(1,0);

    r[0][1]=euler[1];
    for(int i=2; i<=ne; i++)
    {
        log[i]=log[i/2]+1;
        r[0][i]=euler[i];
    }


    for(int p=1; (1<<p)<=ne; p++)
    {
        for(int st=1; st+(1<<p)<=ne; st++)
        {
            if(nivel[ r[p-1][st] ]  < nivel[ r[p-1][st+(1<<(p-1))]] )
                r[p][st]=r[p-1][st];
            else
                r[p][st]=r[p-1][st+(1<<(p-1))];
        }
    }
}


int ask(int a,int b)
{
    int dif;

    a=st[a];
    b=st[b];

    if(a>b)
    {
        dif=a;
        a=b;
        b=dif;
    }

    dif=b-a+1;
    dif=log[dif];

    if(nivel[r[dif][a]] <nivel[ r[dif][b-(1<<dif)+1]]  )
        return r[dif][a];
    else
        return r[dif][b-(1<<dif)+1];
}

int bomb(int a, int b, int)


int main()
{
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);

    make_tat();

    make_lca();


    int X, Y, A, B, C, D,Z;

    scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);

    int stramos;

    for(int i=1; i<=m; i++)
    {
        stramos=ask(X,Y);
        Z=bomb(X,Y,stramos);
        if(i>m-p)
            printf("%d\n",Z);

        X = (X*A + Y*B) % (n + 1);
        Y = (Y*C + Z*D) % (n + 1);
    }


/*
    int a,b,dif;
    for(int i=1; i<=q; i++)
    {
        scanf("%d%d",&a,&b);
        a=st[a];
        b=st[b];

        if(a>b)
        {
            dif=a;
            a=b;
            b=dif;
        }

        dif=b-a+1;
        dif=log[dif];

        if(nivel[r[dif][a]] <nivel[ r[dif][b-(1<<dif)+1]]  )
            printf("%d\n", r[dif][a]);
        else
            printf("%d\n",r[dif][b-(1<<dif)+1] );

    }
*/
    return 0;
}