Cod sursa(job #999551)

Utilizator geniucosOncescu Costin geniucos Data 20 septembrie 2013 18:39:10
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include<cstdio>
#include<vector>
using namespace std;
int z,nr,X,Y,A,B,CC,D,P,x1,y11,i,j,n,m,rmq[128000][18],Q[128000],rmqtata[32009][17],rmqniv[32009][17],niv[32009],T[32009],C[32009],pr[32009],lg[128009];
vector < int > v[32009];
int min(int a,int b)
{
    if(a<b) return a;
    return b;
}
void dfs(int nod)
{
    vector < int > :: iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++)
    {
        niv[*it]=niv[nod]+1;
        dfs(*it);
    }
}
void euler(int nod)
{
    vector < int > :: iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++)
    {
        nr++;
        Q[nr]=nod;
        euler(*it);
    }
    nr++;
    Q[nr]=nod;
}
void dftata(int nod)
{
    int j;
    vector < int > :: iterator it;
    if(niv[nod]!=0)
    {
        rmqtata[nod][0]=T[nod];
        for(j=1;niv[nod]-(1<<j)>=0;j++)
            rmqtata[nod][j]=rmqtata[ rmqtata[nod][j-1] ][j-1];
    }
    for(it=v[nod].begin();it!=v[nod].end();it++)
        dftata(*it);
}
void rmqdf(int nod)
{
    int j;
    vector < int > :: iterator it;
    if(niv[nod]!=0)
    {
        rmqniv[nod][0]=C[nod];
        for(j=1;niv[nod]-(1<<j)>=0;j++)
            rmqniv[nod][j]=min(rmqniv[nod][j-1],rmqniv[ rmqtata[nod][j-1] ][j-1]);
    }
    for(it=v[nod].begin();it!=v[nod].end();it++)
        rmqdf(*it);
}
int minrmq(int st,int dr){return min(rmq[st][lg[dr-st+1]],rmq[dr-(1<<lg[dr-st+1])+1][lg[dr-st+1]]);}
int nivlca(int x,int y){return minrmq(pr[x],pr[y]);}
int alkleastramos(int nod,int k){int i=0;for(i=0;(1<<i)<=k;i++)if(k&(1<<i)) nod=rmqtata[nod][i];return nod;}
int rmqdrumtatafiu(int nod,int nivv)
{
    if(niv[nod]==nivv) return 999999999;
    int o=lg[niv[nod]-nivv];
    return min(rmqniv[nod][o],rmqniv[ alkleastramos(nod,niv[nod]- (nivv+(1<<o)) ) ][o]);
}
int main()
{
freopen("atac.in","r",stdin);
freopen("atac.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&P);
for(i=2;i<=n;i++)
{
    scanf("%d",&x1);
    scanf("%d",&y11);
    T[i]=x1;
    C[i]=y11;
    v[x1].push_back(i);
}
niv[1]=0;
dfs(1);
euler(1);
for(i=nr;i>=1;i--)
    pr[Q[i]]=i;
for(i=1;i<=nr;i++)
{
    lg[i]=lg[i-1];
    if((1<<(lg[i]+1))<=i) lg[i]++;
}
for(i=nr;i>=1;i--)
{
    rmq[i][0]=niv[Q[i]];
    for(j=1;i+(1<<j)-1<=nr;j++)
        rmq[i][j]=min(rmq[i+(1<<(j-1))][j-1],rmq[i][j-1]);
}
dftata(1);
rmqdf(1);
scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&CC,&D);
for(i=1;i<=m;i++)
{
    if(pr[X]<pr[Y]) z=nivlca(X,Y);
    else z=nivlca(Y,X);
    if(X!=Y) z=min(rmqdrumtatafiu(X,z),rmqdrumtatafiu(Y,z));
    else z=0;
    if(i>=m-P+1) printf("%d\n",z);
    x1=(X*A+Y*B)%n+1;X=x1;
    y11=(Y*CC+z*D)%n+1;Y=y11;
}
return 0;
}