Cod sursa(job #3343776)

Utilizator yellowGreenFatu Mihai yellowGreen Data 28 februarie 2026 13:55:56
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
int n,q,p;
int N,idx,mxb;
int X,Y,a,b,c,d,Z;
struct idg
{
    int y,w;
};
vector<idg> G;
vector<int> nxt,top,lvl;
vector<int> anc[18],dp[18];
void add_edge(int x,int y,int w)
{
    idx++;
    G[idx]={y,w};
    nxt[idx]=top[x];
    top[x]=idx;
}
void dfs(int x,int tata)
{
    lvl[x]=lvl[tata]+1;
    for(int i=top[x];i;i=nxt[i])
    {
        auto [y,w]=G[i];
        if(y==tata)
            continue;
        dp[0][y]=w;
        anc[0][y]=x;
        dfs(y,x);
    }
}
int min_lant(int x,int y)
{
    if(x==y)
        return 0;
    int ans=2e9;
    if(lvl[x]<lvl[y])
        swap(x,y);
    int dif=lvl[x]-lvl[y];
    for(int i=0;i<=mxb;i++)
        if(dif&(1<<i))
        {
            ans=min(ans,dp[i][x]);
            x=anc[i][x];
        }
    for(int i=mxb;i>=0;i--)
        if(anc[i][x]!=anc[i][y])
    {
        ans=min(ans,dp[i][x]);
        x=anc[i][x];
        ans=min(ans,dp[i][y]);
        y=anc[i][y];
    }
    if(x!=y)
    {
        ans=min(ans,dp[0][x]);
        ans=min(ans,dp[0][y]);
    }
    return ans;
}
int main()
{
    cin>>n>>q>>p;
    G=vector<idg>(2*n+1);
    nxt=vector<int>(2*n+1);
    top=lvl=vector<int>(n+1);
    for(int i=2;i<=n;i++)
    {
        int x,y,w;
        cin>>y>>w;
        x=i;
        add_edge(x,y,w);
        add_edge(y,x,w);
    }
    mxb=log2(n)+1;
    for(int i=0;i<=mxb;i++)
    {
        anc[i]=vector<int>(n+1);
        dp[i]=vector<int>(n+1);
    }
    dfs(1,0);
    for(int i=1;i<=mxb;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]]);
        }
    }
    int ans=0;
    cin>>X>>Y>>a>>b>>c>>d;
    for(int i=1;i<=q;i++)
    {
        ans=min_lant(X,Y);
        X=(X*a+Y*b)%n+1;
        Y=(Y*c+ans*d)%n+1;
        if(i>=q-p+1)
            cout<<ans<<"\n";
    }
    return 0;
}