Cod sursa(job #3326969)

Utilizator mariusharabariMarius Harabari mariusharabari Data 1 decembrie 2025 16:15:10
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
using namespace std;

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

const int EMAX=15, NMAX=32e3+1, INF=1e5+1;

int n, m, p, x, y, z, a, b, c, d;
int lg[NMAX], dp[EMAX][NMAX], t[EMAX][NMAX], lvl[NMAX];
vector <pair <int,int>> g[NMAX];
bitset <NMAX> viz;

void dfs(int x, int h){
    viz[x]=1;
    lvl[x]=h;
    for(auto vec : g[x]){
        if(!viz[vec.first]){
            t[0][vec.first]=x;
            dp[0][vec.first]=vec.second;
            dfs(vec.first, h+1);
        }
    }
}

int anc(int nod, int ord){
    int e = 0;
    while(ord){
        if(ord%2){
            z=min(z, dp[e][nod]);
            nod=t[e][nod];
        }
        ord/=2;
        e++;
    }
    return nod;
}

int lca(int x, int y){
    int e=lg[lvl[x]];
    while(e>=0){
        if(t[e][x]!=t[e][y]){
            z=min(z, dp[e][x]);
            z=min(z, dp[e][y]);
            x=t[e][x];
            y=t[e][y];
        }
        e--;
    }
    z=min(z, dp[0][x]);
    z=min(z, dp[0][y]);
    return  t[0][x];
}

int main(){
    fin>>n>>m>>p;
    for(int i=2;i<=n;i++){
        fin>>x>>y;
        g[x].push_back({i,y});
        g[i].push_back({x,y});
        //t[0][i]=x;
        //dp[0][i]=y;
    }
    fin>>x>>y>>a>>b>>c>>d;

    for(int i=2;i<=n;i++){
        lg[i]=lg[i/2]+1;
    }

    dfs(1, 1);

    for(int e=1;e<=lg[n];e++){
        //cout<<e<<endl;
        for(int i=1;i<=n;i++){
            t[e][i]=t[e-1][t[e-1][i]];
            dp[e][i]=min(dp[e-1][i], dp[e-1][t[e-1][i]]);
            //cout<<i<<' '<<t[e][i]<<' '<<dp[e][i]<<endl;
        }
    }

    while(m--){
        z=INF;
        if(y==x)
            z=0;

        if(lvl[x]>lvl[y])
            swap(x,y);

        y=anc(y, lvl[y]-lvl[x]);

        lca(y, x);
        if(m<p)
            fout<<z<<'\n';

        x=(a*x+b*y)%n+1;
        y=(c*y+d*z)%n+1;
    }
    return 0;
}