Cod sursa(job #2651284)

Utilizator adiaioanaAdia R. adiaioana Data 21 septembrie 2020 23:36:02
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");

vector <pair<int,int> > eul, L[53000],lmn[20];
int N, lvl[53000],prpoz[53000], str[53000][20],mn[53000][20];
int lim=log2(N);

inline void dfs(int nod, int nvl=0, int ant=0)
{
    lvl[nod]=nvl;
    eul.push_back({nod,nvl+1});
    lmn[0].push_back({nvl+1,nod});
    prpoz[nod]=eul.size()-1;
    for(auto it:L[nod])
        if(it.first!=ant)
        {
            str[it.first][0]=nod;
            mn[it.first][0]=it.second;
            dfs(it.first,nvl+1,nod);
            eul.push_back({nod,nvl+1});
            lmn[0].push_back({nvl+1,nod});
        }
}

inline void prec()
{
    //stramosi
    lim=log2(N);
    for(int i=1; i<=lim; ++i)
        for(int j=1; j<=N; ++j)
        {
            str[j][i]=str[str[j][i-1]][i-1];
            mn[j][i]=min(mn[j][i-1],mn[str[j][i-1]][i-1]);
        }

    int llim=log2(eul.size());
    for(int i=1; i<=llim; ++i)
        for(int j=0; j<eul.size()-(1<<i)+1; ++j)
            lmn[i].push_back(min(lmn[i-1][j],lmn[i-1][j+(1<<i)]));
}

int lca(int nod1, int nod2)
{
    int x=prpoz[nod1], y=prpoz[nod2];
    if(x>y) swap(x,y);
    int lg=log2(y-x+1);
    pair <int,int> el=min(lmn[lg][x],lmn[lg][y-(1<<lg)+1]);
    return el.second;
}

int stramos(int nod, int lg)
{
    int p=0;
    while(lg)
    {
        if(lg&1)
            nod=str[nod][p];
        p++; lg>>=1;
    }
    return nod;
}

inline int solve(int x, int y)
{
    if(x==y)
        return 0;
    int el=lca(x,y);
    int mn1=1e9, mn2=1e9, lg=lvl[x]-lvl[el],p2=log2(lg),u=0;
    if(el!=x){
    int str=stramos(x,lg-(1<<p2));
    mn1=min(mn[x][p2],mn[str][p2]);
    }
    if(el!=y){
    lg=lvl[y]-lvl[el]; p2=log2(lg);
    int str=stramos(y,lg-(1<<p2));
    mn2=min(mn[y][p2],mn[str][p2]);
    }
    return min(mn1,mn2);
}

int main()
{
    int M,P,x,y,a,b,c,d,z;
    cin>>N>>M>>P;
    mn[1][0]=1e9;
    for(int i=2; i<=N; ++i)
    {
        cin>>x>>c;
        L[x].push_back({i,c});
        L[i].push_back({x,c});
    }
    cin>>x>>y>>a>>b>>c>>d;
    dfs(1);
    prec();
    while(M)
    {
        z=solve(x,y);
        x=(x*a+b*y)%N+1;
        y=(y*c+z*d)%N+1;
        if(M<=P)
            cout<<z<<'\n';
        M--;
    }
    return 0;
}