Cod sursa(job #3121038)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 10 aprilie 2023 15:17:07
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
ifstream cin ("atac.in");
ofstream cout ("atac.out");
int cost[20][32010],dp[20][32010],niv[32010],nivmax;
vector <int> lista[32010];
void dfs(int nod,int nivel)
{
    int i;
    nivmax=max(nivmax,nivel);
    niv[nod]=nivel;
    for (i=0; i<lista[nod].size(); i++)
        dfs(lista[nod][i],nivel+1);
}
int query(int x,int y)
{
    int dif,minn,i;
    if (niv[x]>niv[y])
        swap(x,y);
    dif=niv[y]-niv[x];
    minn=INF;
    for (i=0; (1<<i)<=dif; i++)
        if ((dif&(1<<i))!=0)
        {
            minn=min(minn,cost[i][y]);
            y=dp[i][y];
        }
    for (i=15; i>=0; i--)
        if (dp[i][x]!=dp[i][y])
        {
            minn=min(minn,min(cost[i][x],cost[i][y]));
            x=dp[i][x];
            y=dp[i][y];
        }
    if (x!=y)
        minn=min(minn,min(cost[0][x],cost[0][y]));
    if (minn==INF)
        minn=0;
    return minn;
}
int main()
{
    int n,m,p,i,j,x,y,z,a,b,c,d;
    cin>>n>>m>>p;
    for (i=2; i<=n; i++)
    {
        cin>>x>>y;
        lista[x].push_back(i);
        dp[0][i]=x;
        cost[0][i]=y;
    }
    dfs(1,0);
    for (i=1; i<=15; i++)
        for (j=1; j<=n; j++)
        {
            dp[i][j]=dp[i-1][dp[i-1][j]];
            cost[i][j]=min(cost[i-1][j],cost[i-1][dp[i-1][j]]);
        }
    cin>>x>>y>>a>>b>>c>>d;
    for (i=1; i<=m; i++)
    {
        z=query(x,y);
        if (i>=m-p+1)
            cout<<z<<"\n";
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    return 0;
}