Cod sursa(job #3341341)

Utilizator Victor5539Tanase Victor Victor5539 Data 19 februarie 2026 01:06:08
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
//#pragma GCC targe("avx,avx2,fma")

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

const int NMAX=32e3,MMAX=5e5,PMAX=15;
int val[NMAX+5],x,y,a,b,c,d,z=1,new_x,new_y,n,i,m,p,T[NMAX+5],node,cost,nr,E[2*NMAX+5],depth[NMAX+5],start[NMAX+5],nr2,order[NMAX+5],sol[MMAX+5];
bool viz[NMAX+5];
vector <pair<int,int>> adj[NMAX+5];
int r2[PMAX+5][NMAX+5],r3[PMAX+5][NMAX+5];

struct elem{
int node,val;}r[PMAX+5] [2*NMAX+5];

void dfs(int node)
{
    viz[node]=1;
    order[++nr2]=node;
    nr++;
    r[0][nr].node=node;
    r[0][nr].val=depth[node];
    start[node]=nr;



    for (auto edge: adj[node])
    {
        int node2=edge.first;
        if (!viz[node2])
        {
            T[node2]=node;
            val[node2]=edge.second;
            depth[node2]=depth[node]+1;
            dfs(node2);

            nr++;
            r[0][nr].node=node;
            r[0][nr].val=depth[node];
        }
    }
}

int lca(int x, int y)
{
    int st=start[x],dr=start[y];
    if (st>dr)
        swap(st,dr);

    int len=dr-st+1,e=E[len];

    elem cand=r[e][st];

    if (r[e][dr-(1<<e)+1].val<cand.val)
        cand=r[e][dr-(1<<e)+1];

    return cand.node;
}

void build()
{
    for (i=2; i<=nr; i++)
        E[i]=E[i>>1]+1;

    for (int p=1; (1<<p)<=nr; p++)
    {
        for (i=1; i<=nr; i++)
        {
            r[p][i]=r[p-1][i];

            int idx=i+(1<<(p-1));

            if (idx<=nr && r[p-1][idx].val<r[p][i].val)
                r[p][i]=r[p-1][idx];
        }
    }

    for (i=1; i<=n; i++)
        r2[0][i]=T[i];

    for (int p=1; (1<<p)<=n; p++)
    {
        for (i=1; i<=n; i++)
        {
            int node=order[i];
            r2[p][node]=r2[p-1][r2[p-1][node]];
        }
    }

    for (i=1; i<=n; i++)
        r3[0][i]=val[i];

    for (int p=1; (1<<p)<=n; p++)
    {
        for (i=1; i<=n; i++)
        {
            int node=order[i],daddy=r2[p-1][node];
            r3[p][node]=min(r3[p-1][node],r3[p-1][daddy]);
        }
    }
}

int query2(int node, int depth)
{
    int ans=1e9;

    while (depth)
    {
        int lsb=(depth&(-depth)),e=E[lsb];

        ans=min(ans,r3[e][node]);

        node=r2[e][node];
        depth-=lsb;
    }

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr); fout.tie(nullptr);

    fin>>n>>m>>p;

    for (i=2; i<=n; i++)
    {
        fin>>node>>cost;
        adj[node].push_back({i,cost});
        adj[i].push_back({node,cost});
    }

    dfs(1);
    build();

    fin>>x>>y>>a>>b>>c>>d;

    for (i=1; i<=m; i++)
    {
        node=lca(x,y);

        if (x==y)
            z=0;
        else
            z=min(query2(x,depth[x]-depth[node]),query2(y,depth[y]-depth[node]));

        new_x=(1LL*x*a+1LL*y*b)%n+1;
        new_y=(1LL*y*c+1LL*z*d)%n+1;

        sol[i]=z;

        x=new_x; y=new_y;
    }

    for (i=m-p+1; i<=m; i++)
        fout<<sol[i]<<'\n';

    return 0;
}