Cod sursa(job #1951439)

Utilizator robertpop99Popescu Robert Gabriel robertpop99 Data 3 aprilie 2017 16:48:41
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#define maxn 32000
#define mmax 500000
using namespace std;
int n,m,p,x,y,a,b,c,d,x1,y1;
int P[maxn+5][15];
int C[maxn+5][15];
int v[maxn+5][2];
int L[maxn+5];



int LCA(int p, int q)
{
    if(L[p]<L[q])
    {
        int tmp=p;
        p=q;
        q=tmp;
    }

    int log;
    for(log=1;1<<log <= L[p];log++);
    log--;

    for(int i=log;i>=0;i--)
        if(L[p]- (1<<i)>= L[q])
            p=P[p][i];

    if(p==q) return p;

    for(int i=log;i>=0;i--)
        if(P[p][i]!=-1 && P[p][i]!=P[q][i])
            p=P[p][i],q=P[q][i];

    return v[p][0];

}

int caut(int up, int p, int log)
{
    int poz=L[up]+(1<<log),l=p;

    while(L[p]>poz )
    {   if(L[P[p][log]]<poz) log--;
        else p=P[p][log];
    }
    return p;
}
int RMQ(int p, int q)
{   if(p==q) return 0;
    int up=LCA(p,q),cmin=100005;
    int log=0;
    if(p!=1)
    {while(L[p]-(1<<(log+1))>L[up] ) log++;
    cmin=min(cmin,min(C[p][log],C[ caut(up,p,log) ][log]));
    }
    if(q!=1)
    {log=0;
    while(L[q]-(1<<(log+1))>L[up] ) log++;
    cmin=min(cmin,min(C[q][log],C[ caut(up,q,log) ][log]));
    }
    return cmin;
}

int main()
{
    ifstream fin("atac.in");
    ofstream fout("atac.out");
    fin>>n>>m>>p;
    L[1]=0;
    for(int i=2;i<=n;i++)
    {
        int x,z;
        fin>>x>>z;
        v[i][0]=x;
        v[i][1]=z;
        L[i]=L[x]+1;
    }
    v[1][0]=1;
    v[1][1]=0;
    fin>>x>>y>>a>>b>>c>>d;
    for(int i=1;i<=n;i++)
        for(int j=0;1<<j<n;j++)
            P[i][j]=-1;
    for(int i=1;i<=n;i++)
        {P[i][0]=v[i][0];
        C[i][0]=v[i][1];
        }

    for(int j=1;(1<<j) <n;j++)
        for(int i=0;i<=n;i++)
            {if(P[i][j-1]!=-1)
                {P[i][j]=P[ P[i][j-1] ][ j-1 ];
                 C[i][j]=min(C[ caut(P[i][j],i,j-1) ][j-1], C[i][j-1]);
                }
            }
    while(m>p)
    {
        y1=(y*c+RMQ(x,y)*d)%n+1;
        x1=(x*a+y*b)%n+1;
        x=x1,y=y1;
        m--;
    }
    for(int i=1;i<=p;i++)
    {
        int z=RMQ(x,y);

        fout<<z<<'\n';
        y1=(y*c+z*d)%n+1;
        x1=(x*a+y*b)%n+1;
        x=x1,y=y1;

    }
    fin.close();
    fout.close();
    return 0;
}