Cod sursa(job #3241733)

Utilizator Anul2024Anul2024 Anul2024 Data 3 septembrie 2024 11:51:09
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
int t[15][32001],val[15][32001],nivel[32001];
int x,y,a,b,c,d,n,i,nivx,nivy,cost,m,p,pp,z,dif;
vector <pair <int,int>> v[32001];
void dfs (int nod,int tt,int cost,int niv)
{
    t[0][nod]=tt;
    val[0][nod]=cost;
    nivel[nod]=niv;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i].first;
        if (vecin!=tt)
            dfs (vecin,nod,v[nod][i].second,niv+1);
    }
}
int lca (int x,int y)
{
    nivx=nivel[x];
    nivy=nivel[y];
    if (nivx<nivy)
    {
        swap (x,y);
        swap (nivx,nivy);
    }
    cost=100001;
    dif=nivx-nivy;
    for (p=14; p>=0; p--)
    {
        if ((dif>>p)&1)
        {
            cost=min (cost,val[p][x]);
            x=t[p][x];
        }
    }
    if (x==y)
        return cost;
    for (p=14; p>=0; p--)
    {
        if (t[p][x]!=t[p][y])
        {
            cost=min (cost,min (val[p][x],val[p][y]));
            x=t[p][x];
            y=t[p][y];
        }
    }
    cost=min (cost,min (val[0][x],val[0][y]));
    return cost;
}
int main()
{
    fin>>n>>m>>pp;
    for (i=2; i<=n; i++)
    {
        fin>>x>>c;
        v[x].push_back (make_pair (i,c));
        v[i].push_back (make_pair (x,c));
    }
    dfs (1,0,0,1);
    for (p=1; p<=14; p++)
    {
        for (i=1; i<=n; i++)
        {
            val[p][i]=min (val[p-1][i],val[p-1][t[p-1][i]]);
            t[p][i]=t[p-1][t[p-1][i]];
        }
    }
    fin>>x>>y>>a>>b>>c>>d;
    for (i=1; i<=m; i++)
    {
        z=lca (x,y);
        if (i>=m-pp+1)
            fout<<z<<"\n";
        x=(1ll*x*a+1ll*y*b)%n+1;
        y=(1ll*y*c+1ll*z*d)%n+1;
    }
    return 0;
}