Cod sursa(job #3344867)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 6 martie 2026 10:45:46
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <vector>
#define NMAX 32002
using namespace std;
ifstream  fin("atac.in");
ofstream fout("atac.out");
int N,M,P,X,Y,A,B,C,D,Z,tata[NMAX],nivel[NMAX];
vector<pair<int,int>> tree[NMAX];
vector<vector<pair<int,int>>> up(NMAX,vector<pair<int,int>>(17));

void citire()
{
    fin>>N>>M>>P;

    int val;
    for(int i=2; i<=N; i++)
    {
        fin>>tata[i]>>val;

        tree[tata[i]].push_back({i,val});
    }

    fin>>X>>Y>>A>>B>>C>>D;
}

void DFS(int nod)
{
    for(int i=0; i<tree[nod].size(); i++)
    {
        int next_nod=tree[nod][i].first;
        int drum=tree[nod][i].second;

        nivel[next_nod]=nivel[nod]+1;

        up[next_nod][0].first=nod;
        up[next_nod][0].second=drum;
        for(int j=1; j<=16; j++)
        {
            up[next_nod][j].first=up[up[next_nod][j-1].first][j-1].first;
            up[next_nod][j].second=min(up[next_nod][j-1].second,up[up[next_nod][j-1].first][j-1].second);
        }

        DFS(next_nod);
    }
}

int distrugere_drum(int x, int y)
{
    int ans=10000000;

    if(x==y)
    {
        return 0;
    }

    if(nivel[x]<nivel[y])
    {
        swap(x,y);
    }

    int k=nivel[x]-nivel[y];
    for(int j=16; j>=0; j--)
    {
        if(k&(1<<j))
        {
            ans=min(ans,up[x][j].second);
            x=up[x][j].first;
        }
    }

    if(x==y)
    {
        return ans;
    }

    for(int j=16; j>=0; j--)
    {
        if(up[x][j].first!=up[y][j].first)
        {
            ans=min(ans,up[x][j].second);
            ans=min(ans,up[y][j].second);
            x=up[x][j].first;
            y=up[y][j].first;
        }
    }

    ans=min(ans,up[x][0].second);
    ans=min(ans,up[y][0].second);
    return ans;
}

int main()
{
    citire();

    DFS(1);

    Z=distrugere_drum(X,Y);
    if(P==M)
    {
        fout<< Z << "\n";
    }

    for(int i=2; i<=M; i++)
    {
        X=(long long)(X*A+Y*B)%N+1;
        Y=(long long)(Y*C+Z*D)%N+1;

        Z=distrugere_drum(X,Y);

        if(M-P+1<=i)
        {
            fout<< Z << "\n";
        }
    }

    return 0;
}