Cod sursa(job #1951461)

Utilizator robertpop99Popescu Robert Gabriel robertpop99 Data 3 aprilie 2017 17:07:59
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 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 Log[32005];


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 RMQ(int p, int q)
{   if(p==q) return 0;
    int up=LCA(p,q),cmin=100005,a;
    while(p!=up)
    {
        a=Log[ L[p]-L[up] ];
        cmin=min(cmin,C[p][a]);
        p=P[p][a];
    }

    while(q!=up)
    {
        a=Log[ L[q]-L[up] ];
        cmin=min(cmin,C[q][a]);
        q=P[q][a];
    }
    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++)
        Log[i]=Log[i/2]+1;
    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[ P[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;
}