Cod sursa(job #2085835)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 10 decembrie 2017 19:53:41
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
/// Long code incoming
#include<bits/stdc++.h>
#define Nmax (1<<16)
#define LogMax 16
#define x first
#define y second
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int n,q,p;
vector<pair<int,int>>v[Nmax/2];
long long X,Y,A,B,C,D;
inline void Read()
{
    f>>n>>q>>p;
    for(int i=2;i<=n;++i)
    {
        int a,b;
        f>>a>>b;
        v[a].push_back({i,b});
        v[i].push_back({a,b});
    }
    f>>X>>Y>>A>>B>>C>>D;
}
int nod[Nmax],niv[Nmax],Lap[Nmax/2],e;
bool viz[Nmax/2];
int anc[Nmax/2][LogMax],min1[Nmax/2][LogMax];
inline void dfs(int dad, int prec, int vf, int lvl)
{
    ++e;
    nod[e]=vf;
    niv[e]=lvl;
    viz[vf]=1;
    anc[vf][0]=dad;
    min1[vf][0]=prec;
    for(int i=1;i<=15;++i)
    {
        anc[vf][i]=anc[anc[vf][i-1]][i-1];
        min1[vf][i]=min(min1[vf][i-1],min1[anc[vf][i-1]][i-1]);
    }
    for(int i=0;i<v[vf].size();++i)
    {
        if(!viz[v[vf][i].x])
        {
            dfs(vf,v[vf][i].y,v[vf][i].x,lvl+1);
            ++e;
            nod[e]=vf;
            niv[e]=lvl;
        }
    }
    Lap[vf]=e;
}
int RMQ[Nmax][LogMax],LG[Nmax];
inline void rmq()
{
    for(int i=2;i<=e;++i)
        LG[i]=LG[i/2]+1;
    for(int i=1;i<=e;++i)
        RMQ[0][i]=i;
    for(int i=1;(1<<i)<=e;++i)
        for(int j=(1<<i);j<=e;++j)
        {
            int k=(1<<(i-1));
            RMQ[i][j]=RMQ[i-1][j];
            int x=niv[RMQ[i-1][j]];
            int y=niv[RMQ[i-1][j-k]];
            if(x>y)
                RMQ[i][j]=RMQ[i-1][j-k];
        }
}
int query(int x,int y)
{
    if(x==y)
        return 1<<30;
    int dist=niv[Lap[y]]-niv[Lap[x]],sol=1<<30;
   // g<<dist<<" ";
    for(int i=15;i>=0;--i)
        if(dist&(1<<i))
        {
            sol=min(sol,min1[y][i]);
            y=anc[y][i];
            dist-=(1<<i);
        }
    return sol;
}
inline int solve(int x, int y)
{
    int X1,X2,logs,LCA,z1,z2,z3,dif,mina,minb;
    X1=min(Lap[x],Lap[y]);
    X2=max(Lap[x],Lap[y]);
    logs=LG[X2-X1+1];
    LCA=RMQ[logs][X2];
    if(niv[LCA]>niv[RMQ[logs][X1+(1<<logs)-1]])
        LCA=RMQ[logs][X1+(1<<logs)-1];
    z1=niv[Lap[x]];
    z2=niv[Lap[y]];
    z3=niv[LCA];
    LCA=nod[LCA];
    return min(query(LCA,x),query(LCA,y));
}
inline void Queries()
{
    for(int i=1;i<=q;++i)
    {
        long long Z;
        if(X==Y)
            Z=0;
        else
            Z=solve(X,Y);
        if(i>=q-p+1)
            g<<Z<<'\n';
        long long Xp=X;
        long long Yp=Y;
        X=(Xp*A+Yp*B)%n+1;
        Y=(Yp*C+Z*D)%n+1;
    }
}
int main()
{
    Read();
    dfs(0,0,1,0);
    rmq();
    Queries();
    return 0;
}