Cod sursa(job #2330949)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 28 ianuarie 2019 23:41:02
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

const int maxn = 32002;
const int maxlog = 18;
int n, m, p;
int nivel[maxn], str[maxlog][maxn], dst[maxlog][maxn];
int k, E[maxn<<2], L[maxn<<2], P[maxn<<2], rmq[maxlog][maxn<<2], lg[maxn<<2];
vector<int>G[maxn];

void dfs(int nod, int lvl)
{
    ++k;
    E[k]=nod;
    L[k]=lvl;
    P[nod]=k;
    nivel[nod]=lvl;
    for(auto it:G[nod])
    {
        dfs(it, lvl+1);
        ++k;
        E[k]=nod;
        L[k]=lvl;
    }
}

void RMQ()
{
    for(int i=1; i<=k; i++)
    {
        rmq[0][i]=i;
    }
    for(int i=1; (1<<i)<k; i++)
    {
        for(int j=1; j<=k-(1<<i); j++)
        {
            int l=1<<(i-1);
            rmq[i][j]=rmq[i-1][j];
            if(L[rmq[i-1][j+l]]<L[rmq[i][j]])
            {
                rmq[i][j]=rmq[i-1][j+l];
            }
        }
    }
}

int lca(int x, int y)
{
    int a=P[x];
    int b=P[y];
    if(a>b)
    {
        swap(a,b);
    }
    int dif=b-a+1;
    int niv=lg[dif];
    int extra=dif-(1<<niv);
    if(L[rmq[niv][a]]<L[rmq[niv][a+extra]])
    {
        return E[rmq[niv][a]];
    }
    return E[rmq[niv][a+extra]];
}

int main()
{
    int x, y, val, a, b, c, d, z;
    fin>>n>>m>>p;
    for(int i=2; i<=n; i++)
    {
        fin>>x>>val;
        G[x].push_back(i);
        str[0][i]=x;
        dst[0][i]=val;
    }
    fin>>x>>y>>a>>b>>c>>d;
    dfs(1,0);
    for(int i=2; i<=k; i++)
    {
        lg[i]=1+lg[i/2];
    }
    for(int i=1; i<=18; i++)
    {
        for(int j=1; j<=n; j++)
        {
            str[i][j]=str[i-1][str[i-1][j]];
            dst[i][j]=min(dst[i-1][j],dst[i-1][str[i-1][j]]);
        }
    }
    RMQ();
    while(m>0)
    {
        if(x==y)
        {
            z=0;
        }
        else
        {
            z=1000000;
            int st, loga, dif1, dif2, x1, y1;
            st=lca(x,y);
            dif1=nivel[x]-nivel[st];
            x1=x;
            y1=y;
            while(dif1>1)
            {
                loga=1;
                while(loga*2<=dif1)
                {
                    loga=loga*2;
                }
                z=min(z,dst[lg[loga]][x1]);
                x1=str[lg[loga]][x1];
                dif1=dif1-loga;
            }
            if(dif1==1)
            {
                z=min(z,dst[0][x1]);
            }
            dif2=nivel[y]-nivel[st];
            while(dif2>1)
            {
                loga=1;
                while(loga*2<=dif2)
                {
                    loga=loga*2;
                }
                z=min(z,dst[lg[loga]][y1]);
                y1=str[lg[loga]][y1];
                dif2=dif2-loga;
            }
            if(dif2==1)
            {
                z=min(z,dst[0][y1]);
            }
        }
        if(p>=m)
        {
            fout<<z<<'\n';
        }
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        m--;
    }
    return 0;
}