Cod sursa(job #3304789)

Utilizator carinamariaCarina Maria Viespescu carinamaria Data 27 iulie 2025 12:28:45
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
int n, m, p, u, v, x, y, a, b, C, d, X, Y, minn;
int niv[32002], s[32002][17], c[32002][17];
vector<int> L[32002];
void dfs(int nod, int nive){
    niv[nod]=nive;
    for(int i=0;i<L[nod].size();i++){
        if(!niv[L[nod][i]])
            dfs(L[nod][i], nive+1);
    }
}
int main() {
    cin>>n>>m>>p;
    for(int i=2;i<=n;i++){
        cin>>u>>v;
        L[u].push_back(i);
        L[i].push_back(u);
        s[i][0]=u;
        c[i][0]=v;
    }
    dfs(1, 1);
    cin>>x>>y>>a>>b>>C>>d;
    for(int j=1;j<=ceil(log2(n));j++){
        for(int i=1;i<=n;i++){
            s[i][j]=s[s[i][j-1]][j-1];
            c[i][j]=min(c[i][j-1], c[s[i][j-1]][j-1]);
        }
    }
    for(int i=1;i<=m;i++){
        X=x;
        Y=y;
        minn=1e9;
        if(x==y){
            x=(X*a+Y*b)%n+1;
            y=(Y*C)%n+1;
            if(i>=m-p+1)
            cout<<0<<"\n";
            continue;
        }
        if(niv[x]>niv[y]){
            int dif=niv[x]-niv[y];
            for(int j=ceil(log2(n));j>=0;j--){
                if(dif&(1<<j)){
                    minn=min(minn, c[x][j]);
                    x=s[x][j];
                }
            }
        }
        if(niv[x]<niv[y]){
            int dif=niv[y]-niv[x];
            for(int j=ceil(log2(n));j>=0;j--){
                if(dif&(1<<j)){
                    minn=min(minn, c[y][j]);
                    y=s[y][j];
                }
            }
        }
        if(x==y){
            x=(X*a+Y*b)%n+1;
            y=(Y*C+minn*d)%n+1;
            if(i>=m-p+1)
            cout<<minn<<"\n";
            continue;
        }
        for(int j=ceil(log2(n));j>=0;j--){
            if(s[x][j]==s[y][j])
                continue;
            else{
                minn=min(minn, c[x][j]);
                minn=min(minn, c[y][j]);
                x=s[x][j];
                y=s[y][j];
            }
        }
        minn=min(minn, c[x][0]);
        minn=min(minn, c[y][0]);
        x=(X*a+Y*b)%n+1;
        y=(Y*C+minn*d)%n+1;
        if(i>=m-p+1)
            cout<<minn<<"\n";
    }
}