Cod sursa(job #612531)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 8 septembrie 2011 17:13:06
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <cstdio>
#include <vector>

using namespace std;

int l[32001],two[64001],f[15][32001],first[32001],e[64000],ec,rmq[15][64000],v[15][32001];
struct str{int x,d;};
vector <str> g[32001];

inline int min(int x,int y){if (x<y) return x;else return y;}
inline int lca(int x,int y){x=first[x];y=first[y];int aux=two[y-x+1];return min(rmq[aux][x],rmq[aux][y-(1<<aux)+1]);}

void dfs(int x)
{
    vector <str>::iterator it;
    ++ec;
    e[ec]=x;
    first[x]=ec;
    for (it=g[x].begin();it!=g[x].end();++it)
        if (!l[it->d])
        {
            l[it->d]=l[x]+1;
            f[0][it->d]=x;
            v[0][it->d]=it->x;
            dfs(it->d);
            ++ec;
            e[ec]=x;
        }
}

int main()
{
    int n,m,p,i,j,x,y,x2,y2,a,b,c,d,aux,aux2,sol;
    str auxstr;
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    scanf("%d %d %d\n",&n,&m,&p);
    for (i=2;i<2*n;++i)
        two[i]=two[i/2]+1;
    for (i=2;i<=n;++i)
    {
        scanf("%d %d\n",&x,&y);
        auxstr.x=y;
        auxstr.d=x;
        g[i].push_back(auxstr);
        auxstr.d=i;
        g[x].push_back(auxstr);
    }
    l[1]=1;
    v[0][1]=0x3f3f3f3f;
    dfs(1);
    for (i=1;i<2*n;++i)
        rmq[0][i]=l[e[i]];
    for (i=1;1<<i<2*n;++i)
        for (j=1;j<=2*n-(1<<i);++j)
            rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
    for (i=1;1<<i<=n;++i)
    {
        v[i][1]=0x3f3f3f3f;
        for (j=2;j<=n;++j)
        {
            f[i][j]=f[i-1][f[i-1][j]];
            v[i][j]=min(v[i-1][j],v[i-1][f[i-1][j]]);
        }
    }
    scanf("%d %d %d %d %d %d",&x,&y,&a,&b,&c,&d);
    for (i=1;i<=m-p;++i)
    {
        x2=((x*a+y*b)-1)%n+1;
        y2=((x*c+y*d)-1)%n+1;
        x=x2;
        y=y2;
    }
    lca(3,4);
    for (;p;--p)
    {
        if (x==y)
        {
            printf("0\n");
            x2=((x*a+y*b)-1)%n+1;
            y2=((x*c+y*d)-1)%n+1;
            x=x2;
            y=y2;
            continue;
        }
        aux=lca(x,y);
        sol=0x3f3f3f3f;
        while (l[x]>aux)
        {
            aux2=two[l[x]-aux];
            sol=min(sol,v[aux2][x]);
            x=f[aux2][x];
        }
        printf("%d\n",sol);
        x2=((x*a+y*b)-1)%n+1;
        y2=((x*c+y*d)-1)%n+1;
        x=x2;
        y=y2;
    }
    return 0;
}