Cod sursa(job #2974191)

Utilizator alessiamtr12Mitrica Alessia alessiamtr12 Data 3 februarie 2023 15:31:17
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include<vector>
#include<climits>
#define NMAX 32001
#define INF INT_MAX
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n,m,x,y,A,B,C,D,X,Y,p;
vector<int>v[NMAX];
int stramos[30][NMAX],cost[30][NMAX],nivel[NMAX],start[NMAX],finish[NMAX],k;
void dfs(int nod,int niv)
{
    nivel[nod]=niv;
    k++;
    start[nod]=k;
    for(int i=0;i<v[nod].size();i++)
    {
        int nod1=v[nod][i];
        dfs(nod1,niv+1);
    }
    finish[nod]=++k;
}
bool str(int x,int y)
{
    return start[x]<=start[y]&&finish[y]<=finish[x];
}
void calcul_stramosi()
{
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n;j++)
    {
         cost[i][j]=min(cost[i-1][j],cost[i-1][stramos[i-1][j]]);
         stramos[i][j]=stramos[i-1][stramos[i-1][j]];

    }
}
int lca(int x,int y)
{
    if(str(x,y))
        return x;
    if(str(y,x))
        return y;
    for(int p=16;p>=0;p--)
    {
        int z=stramos[p][x];
        if(z&&!str(z,y))
            x=z;
    }
    return stramos[0][x];
}
int costuri(int x,int y)
{
    if(x==y)
        return 0;
    int LCA= lca(x,y);
    int minn=INF;
    for (int nod:{x,y})
    {
        int diff=nivel[nod]-nivel[LCA];
        for (int p=16;p>=0;p--)
        {
            if (diff>=(1<<p))
            {
                diff-=(1<<p);
                minn=min(minn,cost[p][nod]);
                nod=stramos[p][nod];
            }
        }
    }
    return minn;
}
int main()
{
    fin>>n>>m>>p;
    for(int i=2;i<=n;i++)
    {
        fin>>stramos[0][i]>>cost[0][i];
        v[stramos[0][i]].push_back(i);
    }
    dfs(1,1);
    calcul_stramosi();
    fin>>X>>Y>>A>>B>>C>>D;
    for(int i=1;i<=m;i++)
    {
        int sol=costuri(X,Y);
        if(m-i+1<=p)
            fout<<sol<<"\n";
        X=(X*A+Y*B)%n+1;
        Y=(Y*C+sol*D)%n+1;
    }
    return 0;
}