Cod sursa(job #2330951)

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

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

const int maxn = 32002;
const int maxlog = 18;
const int oo = (1<<30);
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 min_edge(int nod, int anc)
{
    if(nod==anc) return oo;
    int log=lg[nivel[nod]-nivel[anc]]+1;
    int nr=nivel[nod]-nivel[anc];
    int edge=(1<<30);
    while(log--)
    {
        if((1<<log)&nr)
        {
            edge=min(edge, dst[log][nod]);
            nod=str[log][nod];
        }
    }
    return edge;
}

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; (1<<i)<=n; 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
        {
            int st;
            st=lca(x,y);
            z=min(min_edge(x,st), min_edge(y,st));
        }
        if(p>=m)
        {
            fout<<z<<'\n';
        }
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        m--;
    }
    return 0;
}