Cod sursa(job #1954774)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 5 aprilie 2017 17:17:49
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("atac.in");
ofstream out("atac.out");

int n,m,p;
int X,Y,A,B,C,D;

vector<int> L[32005];

struct par{
    int nod, cost;
}PAR[32005];

int LOG2[64005];
int es, EULER[64005],NIV[64005],FOCC[32005];
int RMQ[15][65005];

int MIN[15][32005];
int STR[15][32005];

void next(int z){
    X=(X*A + Y*B)%n +1;
    Y=(Y*C + z*D)%n +1;
}
void read(){
    int x,y;
    in>>n>>m>>p;
    for(int i=1;i<n;i++){
        in>>x>>y;
        L[x].push_back(i+1);
        L[i+1].push_back(x);
        PAR[i+1]={x,y};
    }
    in>>X>>Y>>A>>B>>C>>D;
}
void logs(){
    for(int i=2;i<=es;i++){
        LOG2[i]=LOG2[i/2]+1;
    }
}
void euler(int nod, int par, int niv){
    es++;
    EULER[es]=nod;
    NIV[es]=niv;
    if(!FOCC[nod])
        FOCC[nod]=es;
    for(auto x : L[nod]){
        if(x!=par){
            euler(x,nod,niv+1);
            es++;
            EULER[es]=nod;
            NIV[es]=niv;
        }
    }
}
void prep_rmq(){
    for(int i=1;i<=es;i++){
        RMQ[0][i]=i;
    }
    for(int i=1;(1<<i)<=es;i++){
        for(int j=1;j<=es;j++){
            if(NIV[RMQ[i-1][j]] < NIV[RMQ[i-1][j+(1<<(i-1))]])
                RMQ[i][j]=RMQ[i-1][j];
            else RMQ[i][j]=RMQ[i-1][j+(1<<(i-1))];
        }
    }
}
int lca(int x, int y){
    int lo,hi,nr_elem,log_elem;
    lo=min(FOCC[x],FOCC[y]);
    hi=max(FOCC[x],FOCC[y]);
    nr_elem=hi-lo+1;
    log_elem=LOG2[nr_elem];
    if(NIV[RMQ[log_elem][lo]] < NIV[RMQ[log_elem][lo+nr_elem-(1<<log_elem)]])
        return EULER[RMQ[log_elem][lo]];
    else return EULER[RMQ[log_elem][lo+nr_elem-(1<<log_elem)]];
}
void prep_min(){
    for(int i=1;i<=n;i++){
        MIN[0][i]=PAR[i].cost;
        STR[0][i]=PAR[i].nod;
    }
    for(int i=1;(1<<i)<=n;i++){
        for(int j=1;j<=n;j++){
            STR[i][j]=STR[i-1][STR[i-1][j]];
            MIN[i][j]=min(MIN[i-1][j],MIN[i-1][STR[i-1][j]]);
        }
    }
}
int minimum(int nod, int lungime){
    int mini=1<<30,l;
    while(lungime!=0){
        l=LOG2[lungime];
        mini=min(mini,MIN[l][nod]);
        lungime-=(1<<l);
        nod=STR[l][nod];
    }
    return mini;
}
void prep(){
    euler(L[2].front(),-1,1);
    logs();
    prep_rmq();
    prep_min();
}
void solve(){
    int lc,d1,d2;
    prep();
    for(int i=1;i<=m-p;i++){
        lc=lca(X,Y);
        d1=NIV[FOCC[X]]-NIV[FOCC[lc]];
        d2=NIV[FOCC[Y]]-NIV[FOCC[lc]];
        next(min(minimum(X,d1),minimum(Y,d2)));
    }
    for(int i=1;i<=p;i++){
        int m1,m2;
        lc=lca(X,Y);
        d1=NIV[FOCC[X]]-NIV[FOCC[lc]];
        d2=NIV[FOCC[Y]]-NIV[FOCC[lc]];
        m1=minimum(X,d1);
        m2=minimum(Y,d2);
        next(min(m1,m2));
        out<<min(m1,m2)<<"\n";
    }
}
int main(){
    read();
    solve();
    return 0;
}