Cod sursa(job #2330733)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 28 ianuarie 2019 19:55:00
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 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], lg[maxn];
vector<pair<int,int> >G[maxn];

void dfs(int nod, int lvl, int tata)
{
    ++k;
    E[k]=nod;
    L[k]=lvl;
    P[nod]=k;
    nivel[nod]=lvl;
    for(auto it:G[nod])
    {
        if(it.first!=tata)
        {
            str[0][it.first]=nod;
            dst[0][it.first]=it.second;
            dfs(it.first, lvl+1, nod);
            ++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,val});
        G[i].push_back({x,val});
    }
    fin>>x>>y>>a>>b>>c>>d;
    dfs(1,0,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=1000000000;
            int st=lca(x,y), loga, difn;
            int dif1=nivel[x]-nivel[st];
            int x1=x;int y1=y;
            while(dif1>0)
            {
                loga=1;
                difn=0;
                while(loga*2<=dif1)
                {
                    loga=loga*2;
                    difn++;
                }
                z=min(z,dst[difn][x1]);
                x1=str[difn][x1];
                dif1=dif1-loga;
            }
            int dif2=nivel[y]-nivel[st];
            while(dif2>0)
            {
                loga=1;
                difn=0;
                while(loga*2<=dif2)
                {
                    loga=loga*2;
                    difn++;
                }
                z=min(z,dst[difn][y1]);
                y1=str[difn][y1];
                dif2=dif2-loga;
            }
        }
        if(p>=m)
        {
            fout<<z<<'\n';
        }
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        m--;
    }
    return 0;
}