Cod sursa(job #1145850)

Utilizator cat_red20Vasile Ioana cat_red20 Data 18 martie 2014 14:47:24
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include<fstream>
#include<vector>
#define MAXN 32001
using namespace std;
int n,x,y,z,a,b,c,d,m,nr,u,maxlvl;
int din[MAXN][20],p[MAXN][20],lvl[2*MAXN][20],eul[2*MAXN][20],poz[MAXN];
vector<pair<int,int> >g[MAXN];
ifstream fin("atac.in");
ofstream fout("atac.out");
void citire()
{
    int p,q;
    fin>>n>>m>>nr;
    for(int i=2;i<=n;i++)
    {
        fin>>p>>q;
        g[i].push_back(make_pair(p,q));
        g[p].push_back(make_pair(i,q));
    }
    fin>>x>>y>>a>>b>>c>>d;
}

void dfs(int nod,int niv)
{
    if(niv>maxlvl)
    maxlvl=niv;
    eul[++u][0]=nod;
    lvl[u][0]=niv;
    poz[nod]=u;
    for(int i=0;i<g[nod].size();i++)
    {
        if(poz[g[nod][i].first]==0)
        {
            p[g[nod][i].first][0]=nod;
            din[g[nod][i].first][0]=g[nod][i].second;
            dfs(g[nod][i].first,niv+1);
            eul[++u][0]=nod;
            lvl[u][0]=niv;
        }
    }
}

void rmq()
{
    int p2;
    for(int i=1;(1<<i)<=u;i++)
    {
        p2=(1<<(i-1));
        for(int j=1;j<=u-p2;j++)
        {
            if(lvl[j][i-1]<lvl[j+p2][i-1])
            {
                lvl[j][i]=lvl[j][i-1];
                eul[j][i]=eul[j][i-1];
            }
            else
            {
                lvl[j][i]=lvl[j+p2][i-1];
                eul[j][i]=eul[j+p2][i-1];
            }
        }
    }
}

void preproc()
{
    for(int i=1;(1<<i)<=maxlvl;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((1<<i)>lvl[poz[j]][0])
            continue;
            p[j][i]=p[p[j][i-1]][i-1];
            din[j][i]=min(din[j][i-1],din[p[j][i-1]][i-1]);
        }
    }
}
inline int pow2(int x)
{
    int i;
    for( i=0;(1<<i)<=x;i++);
    return i-1;
}

inline int Minim(int x,int y)
{
    int sol=1000000;
    int niv=lvl[poz[x]][0]-lvl[poz[y]][0];
    for(int i=pow2(niv);x!=y;x=p[x][i])
    {
        sol=min(sol,din[x][i]);
        niv=lvl[poz[x]][0]-lvl[poz[y]][0];
        i=pow2(niv);
    }
return sol;
}

int query(int x,int y)
{
    int st=min(poz[x],poz[y]),sf=poz[x]+poz[y]-st;
    int l=pow2(sf-st+1);
    int lca=(lvl[st][l]<lvl[sf-(1<<l)+1][l])?eul[st][l]:eul[sf-(1<<l)+1][l];
    return min(Minim(x,lca),Minim(y,lca));
}

int main()
{
    citire();
    dfs(1,1);
    rmq();
    preproc();
    for(int i=1;i<=m;i++)
    {
        z=query(x,y);
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        if(i>=m-nr+1)
        fout<<z<<"\n";
    }
    return 0;
}