Cod sursa(job #881275)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 17 februarie 2013 20:59:08
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <vector>
 
using namespace std;
 
int l[32001],two[64000],f[15][32001],first[32000],e[64000],ec,rmq[16][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 void swap(int &x,int &y){int aux=x;x=y;y=aux;}
inline int lca(int x,int y){x=first[x];y=first[y];if (x>y) swap(x,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 (;m;--m)
    {
        if (x==y)
            sol=0;
        else
        {
            x2=x;
            y2=y;
            aux=lca(x,y);
            sol=0x3f3f3f3f;
            while (l[x2]>aux)
            {
                aux2=two[l[x2]-aux];
                sol=min(sol,v[aux2][x2]);
                x2=f[aux2][x2];
            }
            while (l[y2]>aux)
            {
                aux2=two[l[y2]-aux];
                sol=min(sol,v[aux2][y2]);
                y2=f[aux2][y2];
            }
        }
        if (m<=p)
            printf("%d\n",sol);
        x2=(x*a+y*b)%n+1;
        y2=(y*c+sol*d)%n+1;
        x=x2;
        y=y2;
    }
    return 0;
}