Cod sursa(job #382980)

Utilizator freak93Adrian Budau freak93 Data 15 ianuarie 2010 11:11:27
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include<fstream>
#include<vector>

using namespace std;

const char iname[]="atac.in";
const char oname[]="atac.out";
const int maxn=33000;
const int maxl=16;
const int INF=(1<<31)-1;

ifstream f(iname);
ofstream g(oname);

//distanta lca
struct dis
{
    int w;
    int dis;
} anc[maxl][maxn];
int log[maxn*2];

//variabile normale
int i,j,n,m,a,b,c,d,p,x,y,z;

//rmq
int sons[maxn],height[maxn],euler[maxn*2],rmq[maxl*2][maxn*2],k;
int pos[maxn];
vector<int> E[maxn];

void get_height(int x)
{
    if(height[x])
        return;
    if(anc[0][x].w==0)
    {
        height[x]=1;
        return;
    }

    if(height[anc[0][x].w]==0)
        get_height(anc[0][x].w);
    height[x]=height[anc[0][x].w]+1;
}

void build_euler(int x)
{
    euler[++k]=x;
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        build_euler(*it),euler[++k]=x;
    pos[x]=k;
}

int lca(int x,int y)
{
    int aux;
    if(x>y)
        aux=x,x=y,y=aux;
    int dis=y-x+1;
    int r=rmq[log[dis]][y-(1<<log[dis])+1];
    if(height[euler[rmq[log[dis]][x]]]<height[euler[r]])
        r=rmq[log[dis]][x];
    return r;
}

int dis(int x,int y)
{
    int dis=height[x]-height[y];
    int step,rez=x,ans=INF;
    for(step=0;(1<<step)<=dis;++step)
        if((1<<step)&dis)
            ans=min(ans,anc[step][rez].dis),rez=anc[step][rez].w;
    return ans;
}

int main()
{
    f>>n>>m>>p;
    for(i=2;i<=n;++i)
        f>>anc[0][i].w>>anc[0][i].dis,++sons[anc[0][i].w],E[anc[0][i].w].push_back(i);

    for(i=2;i<=n+n;++i)
        log[i]=log[i>>1]+1;
    for(i=1;i<=log[n];++i)
        for(j=n;j;--j)
            anc[i][j].w=anc[i-1][anc[i-1][j].w].w,anc[i][j].dis=min(anc[i-1][j].dis,anc[i-1][anc[i-1][j].w].dis);

    for(i=1;i<=n;++i)
        get_height(i);

    build_euler(1);
    for(i=1;i<=k;++i)
        rmq[0][i]=i;
    for(i=1;i<=log[k];++i)
        for(j=k-(1<<i)+1;j;--j)
        {
            rmq[i][j]=rmq[i-1][j];
            if(height[euler[rmq[i-1][j+(1<<i-1)]]]<height[euler[rmq[i-1][j]]])
                rmq[i][j]=rmq[i-1][j+(1<<i-1)];
        }

    m-=p;
    f>>x>>y>>a>>b>>c>>d;
    for(i=1;i<=m;++i)
    {
        z=euler[lca(pos[x],pos[y])];
        z=min(dis(x,z),dis(y,z));
        if(z==INF)
            z=0;
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }

    for(i=1;i<=p;++i)
    {
        z=euler[lca(pos[x],pos[y])];
        z=min(dis(x,z),dis(y,z));
        if(z==INF)
            z=0;
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        g<<z<<"\n";
    }

    f.close();
    g.close();

    return 0;
}