Cod sursa(job #3322734)

Utilizator yellowGreenFatu Mihai yellowGreen Data 15 noiembrie 2025 14:02:20
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int NMAX = 32005;
int n,m,p,x,y,a,b,c,d,ans;
vector<int> G[NMAX];
int lg2[NMAX],niv[NMAX];
int anc[20][NMAX],dp[20][NMAX];
void dfs(int x,int tata,int h)
{
    niv[x]=h;
    for(auto y:G[x])
    {
        if(y==tata)
            continue;
        dfs(y,x,h+1);
    }
}
int min_lant(int x,int y)
{
    int ans=2e9;
    if(niv[x]<niv[y])
        swap(x,y);
    int dif=niv[x]-niv[y];
    for(int i=0;i<=18;i++)
        if(dif&(1<<i))
        {
            ans=min(ans,dp[i][x]);
            x=anc[i][x];
        }
    if(x==y) return ans;
    for(int i=18;i>=0;i--)
    {
        if(anc[i][x]!=anc[i][y])
        {
            ans=min(ans,dp[i][x]);
            ans=min(ans,dp[i][y]);
            x=anc[i][x];
            y=anc[i][y];
        }
    }
    ans=min(ans,dp[0][x]);
    ans=min(ans,dp[0][y]);
    return ans;
}
int main()
{
    cin>>n>>m>>p;
    anc[0][1]=1;
    dp[0][1]=2e9;
    for(int i=2;i<=n;i++)
    {
        int y,v;
        cin>>y>>v;
        anc[0][i]=y;
        dp[0][i]=v;
    }
    cin>>x>>y>>a>>b>>c>>d;
    dfs(1,0,1);
    for(int i=1;i<=18;i++)
        for(int j=1;j<=n;j++)
    {
        anc[i][j]=anc[i-1][anc[i-1][j]];
        dp[i][j]=min(dp[i-1][j],dp[i-1][anc[i-1][j]]);
    }
    for(int i=1;i<=m;i++)
    {
        ans=min_lant(x,y);
        //cout<<x<<" "<<y<<" "<<ans<<"\n";
        if(i>=m-p+1)
            cout<<ans<<"\n";
        x=(x*a+y*b)%n+1;
        y=(y*c+ans*d)%n+1;
    }
    return 0;
}