Cod sursa(job #3316398)

Utilizator tudor_costinCostin Tudor tudor_costin Data 18 octombrie 2025 17:42:04
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int Nmax=4e4+5,inf=1e7;
vector<pair<int,int>> g[Nmax];
int up[Nmax][20],dp[Nmax][20];
int tin[Nmax],tout[Nmax];
int timer=0;
void dfs(int nod,int pr,int val)
{
    up[nod][0]=pr;
    dp[nod][0]=val;
    tin[nod]=++timer;
    for(int i=1;i<=17;i++)
    {
        up[nod][i]=up[up[nod][i-1]][i-1];
        dp[nod][i]=min(dp[nod][i-1],dp[up[nod][i-1]][i-1]);
    }
    for(auto [u,w]:g[nod])
    {
        if(u!=pr)
        {
            dfs(u,nod,w);
        }
    }
    tout[nod]=timer;
}
bool upper(int a,int b)
{
    return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}
int lca(int x,int y)
{
    if(upper(x,y)) return x;
    if(upper(y,x)) return y;
    for(int i=17;i>=0;i--)
    {
        if(!upper(up[x][i],y))
        {
            x=up[x][i];
        }
    }
    return up[x][0];
}
int getans(int u,int x)
{
    if(x==u) return inf;
    int ans=inf;
    for(int i=17;i>=0;i--)
    {
        if(!upper(up[x][i],u))
        {
            ans=min(ans,dp[x][i]);
            x=up[x][i];
        }
    }
    ans=min(ans,dp[x][0]);
    return ans;
}
int main()
{
    int n,m,p;
    fin>>n>>m>>p;
    for(int i=2;i<=n;i++)
    {
        int x,v;
        fin>>x>>v;
        g[i].push_back({x,v});
        g[x].push_back({i,v});
    }
    dfs(1,1,inf);
    deque<int> ans;
    int x,y,a,b,c,d;
    fin>>x>>y>>a>>b>>c>>d;
    int l=lca(x,y);
    int sol=0;
    if(x!=y)
    {
        sol=min(getans(l,x),getans(l,y));
    }
    ans.push_back(sol);
    m--;
    while(m--)
    {
        x=(x*a+y*b)%n + 1;
        y=(y*c+sol*d)%n +1;
        sol=0;
        l=lca(x,y);
        if(x!=y)
        {
            sol=min(getans(l,x),getans(l,y));
        }
        ans.push_back(sol);
        if(ans.size()>p) ans.pop_front();
    }
    while(!ans.empty())
    {
        fout<<ans.front()<<'\n';
        ans.pop_front();
    }
    return 0;
}