Cod sursa(job #186226)

Utilizator AlxCojocaru Alexandru Alx Data 26 aprilie 2008 22:53:40
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <stdio.h>
struct nod
{
    int val,cost;
    nod *urm;
};
nod *g[32001],*pt;
int n,m,p,x,y,a,b,c,d,vc,cs,eul[100000],ad[100000],niv=1,pe,nv[32001],p1,p2,rmq[16][32001],lg[32001],z,t[32001][2],st[16][32001],lca,z1,mx;
void euler(int nd)
{
    ad[pe]=niv;
    eul[pe]=nd;
    nv[nd]=niv;
    pe++;
    nod *p2=g[nd];
    while (p2)
    {
        if (!nv[p2->val])
        {
            niv++;
            if (mx<niv)
                mx=niv;
            t[p2->val][0]=nd;
            t[p2->val][1]=p2->cost;
            euler(p2->val);
            niv--;
            ad[pe]=niv;
            eul[pe]=nd;
            pe++;
        }
        p2=p2->urm;
    }
}
int main()
{
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    scanf("%d %d %d\n",&n,&m,&p);
    int i,j,k,tata,l,ds;
    for (i=2;i<=n;i++)
    {
        scanf("%d %d\n",&vc,&cs);
        pt=new nod;
        pt->val=vc;
        pt->cost=cs;
        pt->urm=g[i];
        g[i]=pt;
        pt=new nod;
        pt->val=i;
        pt->cost=cs;
        pt->urm=g[vc];
        g[vc]=pt;
    }
    scanf("%d %d %d %d %d %d\n",&x,&y,&a,&b,&c,&d);
    euler(1);
    lg[1]=0;
    for (j=1;j<=n;j++)
    {
        rmq[0][j]=ad[j];
        st[0][j]=t[j][1];
        if (j>1)
            lg[j]=lg[j/2]+1;
    }
    st[0][1]=100001;
    for (j=1;(1<<j)<=n;j++)
        for (k=1;k<=n-(1<<j)+1;k++)
            rmq[j][k]=rmq[j-1][k]<rmq[j-1][k+(1<<(j-1))] ? rmq[j-1][k] : rmq[j-1][k+(1<<(j-1))];
    for (j=1;(1<<j)<=mx;j++)
        for (k=1;k<=n;k++)
        {
            tata=k;
            for (l=0;l<1<<(j-1);l++)
                tata=t[tata][0];
            st[j][k]=st[j-1][k]<st[j-1][tata] ? st[j-1][k] : st[j-1][tata];
        }
    for (i=1;i<=m;i++)
    {
        if (x!=y)
        {
            p1=p2=0;
            for (j=0;!p1||!p2;j++)
                if (eul[j]==x)
                    p1=j;
                else
                    if (eul[j]==y)
                        p2=j;
            int min=p1<p2 ? p1 : p2,max;
            if (min==p1)
                max=p2;
            else
                max=p1;
            ds=max-min+1;
            lca=rmq[lg[ds]][min]<rmq[lg[ds]][max-(1<<lg[ds])+1] ? rmq[lg[ds]][min] : rmq[lg[ds]][max-(1<<lg[ds])+1];
            for (j=min;;j++)
                if (ad[j]==lca)
                {
                    lca=eul[j];
                    break;
                }
            ds=nv[x]-nv[lca];
            z=st[lg[ds]][x];
            while (ds)
            {
                for (j=0;j<lg[ds];j++)
                    x=t[x][0];
                ds-=1<<lg[ds];
                z=z<st[lg[ds]][x] ? z : st[lg[ds]][x];
            }
            ds=nv[y]-nv[lca ];
            z1=st[lg[ds]][y];
            while (ds)
            {
                for (j=0;j<lg[ds];j++)
                    y=t[y][0];
                ds-=1<<lg[ds];
                z1=z1<st[lg[ds]][y] ? z1 : st[lg[ds]][y];
            }
            z=z<z1 ? z : z1;
        }
        else
            z=0;
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        if (i>m-p)
            printf("%d\n",z);
    }
    return 0;
}