Cod sursa(job #3322413)

Utilizator yellowGreenFatu Mihai yellowGreen Data 13 noiembrie 2025 21:03:35
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
int n,m,p,x,y,A,B,C,D;
struct idk
{
    int y,v;
};
struct muchii
{
    int x,y,v;
}T[32005];
vector<idk> G[32005];
int niv[64005],E[64005],tint[32005],tout[32005],N;
int spt[15][64005],lg2[64005],mxb;
int aint[400005],lazy[400005];
void propagate(int node,int st,int dr)
{
    if(lazy[node]==2e9)
        return;
    aint[node]=min(aint[node],lazy[node]);
    if(st==dr)
    {
        lazy[node]=2e9;
        return;
    }
    lazy[2*node]=min(lazy[2*node],lazy[node]);
    lazy[2*node+1]=min(lazy[2*node+1],lazy[node]);
    lazy[node]=2e9;
    return;
}
void update(int node,int st,int dr,int x,int y,int v)
{
    propagate(node,st,dr);
    if(st>=x && dr<=y)
    {
        lazy[node]=min(lazy[node],v);
        propagate(node,st,dr);
        return;
    }
    if(st>y || dr<x)
        return;
    int mij=(st+dr)>>1;
    update(2*node,st,mij,x,y,v);
    update(2*node+1,mij+1,dr,x,y,v);
    aint[node]=min(aint[2*node],aint[2*node+1]);
}
int query(int node,int st,int dr,int x,int y)
{
    propagate(node,st,dr);
    if(st>=x && dr<=y)
        return aint[node];
    if(st>y || dr<x)
        return 2e9;
    int mij=(st+dr)>>1;
    return min(query(2*node,st,mij,x,y),query(2*node+1,mij+1,dr,x,y));
}
void dfs(int x,int tata,int h)
{
    N++;
    niv[N]=h;
    E[N]=x;
    tint[x]=N;
    for(auto [y,v]:G[x])
    {
        if(y==tata)
            continue;
        dfs(y,x,h+1);
        N++;
        niv[N]=h;
        E[N]=x;
    }
    tout[x]=N;
}
void rmq()
{
    for(int i=2;i<=N;i++)
        lg2[i]=1+lg2[i>>1];
    mxb=lg2[N];
    for(int i=1;i<=N;i++)
        spt[0][i]=i;
    for(int i=1;i<=mxb;i++)
        for(int j=1;j+(1<<i)-1<=N;j++)
    {
        int h1=spt[i-1][j];
        int h2=spt[i-1][j+(1<<(i-1))];
        if(niv[h1]<niv[h2])
            spt[i][j]=h1;
        else
            spt[i][j]=h2;
    }
}
int LCA(int x,int y)
{
    int px=tint[x];
    int py=tint[y];
    if(px>py)
        swap(px,py);
    int sz=py-px+1;
    int lg=lg2[sz];
    int h1=spt[lg][px];
    int h2=spt[lg][py-(1<<lg)+1];
    if(niv[h1]<niv[h2])
        return E[h1];
    else
        return E[h2];
}
int main()
{
    cin>>n>>m>>p;
    for(int i=1;i<=8*n;i++)
    {
        aint[i]=2e9;
        lazy[i]=2e9;
    }
    for(int i=2;i<=n;i++)
    {
        int y,v;
        cin>>y>>v;
        T[i-1]={y,i,v};
        G[i].emplace_back(y,v);
        G[y].emplace_back(i,v);
    }
    cin>>x>>y>>A>>B>>C>>D;
    dfs(1,0,1);
    rmq();
    for(int i=1;i<=n-1;i++)
    {
        int x=T[i].x;
        int y=T[i].y;
        int v=T[i].v;
        update(1,1,N,tint[x],tout[x]+1,v);
    }
    int nx=x,ny=y,ans=0;
    for(int i=1;i<=m;i++)
    {
        x=nx;
        y=ny;
        int lca=LCA(x,y);
        ans=min(query(1,1,N,tint[lca],tint[x]),query(1,1,N,tint[lca],tint[y]));
        nx=(x*A+y*B)%n+1;
        ny=(y*C+ans*D)%n+1;
        if(i>=m-p+1)
            cout<<ans<<"\n";
    }
    return 0;
}