Cod sursa(job #2644332)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 24 august 2020 12:09:23
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda prbd2 Marime 2.47 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
struct drum
{
    int x, val;
    drum(int x, int val)
    {
        this->x=x;
        this->val=val;
    }
};
struct nodS
{
    int h=0;
    int prev[18];
    int premin[18];
    vector<drum> vecini;
};
int n,m,p,x,y,ans,a,b,c,d,i,val,lca;
nodS nod[32005];
void dfs(int p, int par, int lval)
{
    nod[p].h=nod[par].h+1;

    if(p!=1)
    {
        nod[p].prev[0]=par;
        nod[p].premin[0]=lval;

        for(int i=1;i<=15;i++)
        {
            nod[p].prev[i]=nod[nod[p].prev[i-1]].prev[i-1];

            if(nod[p].prev[i]==0)
                break;

            nod[p].premin[i]=min(nod[p].premin[i-1], nod[nod[p].prev[i-1]].premin[i-1]);
        }
    }

    for(auto it : nod[p].vecini)
    {
        if(it.x!=par)
            dfs(it.x, p, it.val);
    }
}
int anc(int p, int val)
{
    for(int i=0;i<=15;i++)
    {
        if((val>>i)&1)
        {
            p=nod[p].prev[i];
        }
    }

    return p;
}
int ancmin(int p, int val)
{
    int ans=1e6;

    for(int i=0;i<=15;i++)
    {
        if((val>>i)&1)
        {
            ans=min(ans, nod[p].premin[i]);
            p=nod[p].prev[i];
        }
    }

    return ans;
}
int flca(int x, int y)
{
    if(nod[x].h>nod[y].h)
        swap(x, y);

    y=anc(y, nod[y].h-nod[x].h);

    if(x==y)
        return x;

    for(int i=15;i>=0;i--)
    {
        if(nod[x].prev[i]!=nod[y].prev[i])
        {
            x=nod[x].prev[i];
            y=nod[y].prev[i];
        }
    }

    return nod[x].prev[0];
}
int main()
{
    fin>>n>>m>>p;
    for(i=2;i<=n;i++)
    {
        fin>>x>>val;
        nod[x].vecini.push_back(drum(i, val));
        nod[i].vecini.push_back(drum(x, val));
    }

    dfs(1, 0, 0);

    fin>>x>>y>>a>>b>>c>>d;
    while(m)
    {
        ans=0;
        if(x!=y)
        {
            lca=flca(x, y);
            if(x==lca)
                ans=ancmin(y, nod[y].h-nod[lca].h);
            else if(y==lca)
                ans=ancmin(x, nod[x].h-nod[lca].h);
            else
            {
                ans=min(ancmin(x, nod[x].h-nod[lca].h), ancmin(y, nod[y].h-nod[lca].h));
            }
        }

        if(m<=p)
            fout<<ans<<'\n';

        //cout<<x<<' '<<y<<' '<<lca<<' '<<ans<<'\n';

        x=(x*a + y*b)%n +1;
        y=(y*c + ans*d)%n +1;

        m--;
    }
    return 0;
}