Cod sursa(job #3344862)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 6 martie 2026 10:20:52
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 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,nivel[NMAX],parent[NMAX],cost[NMAX];
vector<pair<int,int>> tree[NMAX];

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

    int u,v;
    for(int i=2; i<=N; i++)
    {
        fin>>u>>v;

        tree[u].push_back({i,v});
        tree[i].push_back({u,v});
    }

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

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

        if(next_nod!=tata)
        {
            parent[next_nod]=nod;
            nivel[next_nod]=nivel[nod]+1;
            cost[next_nod]=drum;

            DFS(nod,next_nod);
        }
    }
}

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

    while(x!=y)
    {
        if(nivel[x]>=nivel[y])
        {
            ans=min(ans,cost[x]);
            x=parent[x];
        }
        else
        {
            ans=min(ans,cost[y]);
            y=parent[y];
        }
    }

    return ans;
}

int main()
{
    citire();

    DFS(0,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;
}