Cod sursa(job #2867987)

Utilizator GligarEsterabadeyan Hadi Gligar Data 10 martie 2022 17:52:48
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int nmax=32000, n2max=15, inf=(1<<30)-1;

vector <int> g[nmax+1];

int rmq[n2max+1][2*nmax], pv[nmax+1], l[nmax+1], lg[2*nmax];
int v[n2max][nmax+1],f[n2max][nmax+1];

int poz=0;
void dfs(int x){
    poz++;
    rmq[0][poz]=x;
    pv[x]=poz;
    for(int i=0;i<int(g[x].size());i++){
        int xn=g[x][i];
        l[xn]=l[x]+1;
        dfs(xn);
        poz++;
        rmq[0][poz]=x;
    }
}

int Min(int a,int b){
    if(a<b){
        return a;
    }else{
        return b;
    }
}

int main(){
    int n,m,p;
    fin>>n>>m>>p;
    for(int i=2;i<=n;i++){
        int x,y;
        fin>>x>>y;
        g[x].push_back(i);
        v[0][i]=y;
        f[0][i]=x;
    }
    v[0][0]=inf;
    v[0][1]=inf;
    for(int i=2;i<2*nmax;i++){
        lg[i]=lg[i/2]+1;
    }
    for(int i=1;i<=lg[n];i++){
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][f[i-1][j]];
            v[i][j]=Min(v[i-1][j],v[i-1][f[i-1][j]]);
        }
    }
    l[1]=1;
    dfs(1);
    for(int i=1;i<=lg[poz];i++){
        for(int j=1;j<=poz-(1<<i)+1;j++){
            if(l[rmq[i-1][j]]<l[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 x,y,a,b,c,d;
    fin>>x>>y>>a>>b>>c>>d;
    for(int i=1;i<=m;i++){
        int x2=x,y2=y;
        x=pv[x];
        y=pv[y];
        if(x>y){
            int aux=x;
            x=y;
            y=aux;
        }
        int log2=lg[y-x+1],lca;
        if(l[rmq[log2][x]]<l[rmq[log2][y+1-(1<<log2)]]){
            lca=rmq[log2][x];
        }else{
            lca=rmq[log2][y+1-(1<<log2)];
        }
        x=x2;
        y=y2;
        int aux=l[x]-l[lca], auy=l[y]-l[lca];
        int minx=inf;
        for(int j=0;(1<<j)<=aux;j++){
            if((aux&(1<<j))!=0){
                minx=Min(minx,v[j][x]);
                x=f[j][x];
            }
        }
        for(int j=0;(1<<j)<=auy;j++){
            if((auy&(1<<j))!=0){
                minx=Min(minx,v[j][y]);
                y=f[j][y];
            }
        }
        if(minx==inf){
            minx=0;
        }
        if(i>=m-p+1){
            fout<<minx<<"\n";
        }
        x=(x2*a+y2*b)%n+1;
        y=(y2*c+minx*d)%n+1;
    }
    return 0;
}