Cod sursa(job #2409955)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 19 aprilie 2019 16:19:37
Problema Atac Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>
#define Dim 32007
#define MAX 2000000000
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int N,M,P,X,Y,X1,Y1,A,B,C,D,Z,a,b;
int E[2*Dim],Prim[Dim],G[2*Dim],cnt,Level[Dim];
int rmq[16][Dim],cost[16][Dim],T[16][Dim],deepA,deepB;
int vertex,deepL,ans;
typedef pair<int,int> pi;
bool viz[Dim],viz2[Dim],viz3[Dim];

vector < pi > V[Dim];
set < pi > S[Dim];
set < pi > ::iterator it;

void DFS(int nod,int niv)
{
    viz[nod]=1;
    Level[nod]=niv;
    G[++cnt]=niv;
    E[cnt]=nod;
    Prim[nod]=cnt;
    for(unsigned int i=0;i<V[nod].size();i++)
    {
        int vecin=V[nod][i].first;
        if(!viz[vecin])
        {
            cost[0][vecin]=V[nod][i].second;
            T[0][vecin]=nod;
            DFS(vecin,niv+1);
            E[++cnt]=nod;
            G[cnt]=niv;
        }
    }
}

void RMQ()
{
    for(int i=1;i<=cnt;i++) rmq[0][i]=i;
    for(int i=1;(1<<i)<=cnt;i++)
    for(int j=1;j+(1<<i)-1<=cnt;j++)
    {
       int a=rmq[i-1][j];
       int b=rmq[i-1][j+(1<<(i-1))];
       if(G[a]<=G[b]) rmq[i][j]=a;
       else rmq[i][j]=b;
    }
}

void COST()
{
    for(int i=1;(1<<i)<=N;i++)
    for(int j=1;j<=N;j++)
    {
        T[i][j]=T[i-1][T[i-1][j]];
        cost[i][j]=min(cost[i-1][j],cost[i-1][T[i-1][j]]);
    }
}

void LCA(int poza,int pozb)
{

    if(poza>pozb)
    {
        swap(poza,pozb);
    }
    int dif=log2(pozb-poza+1);
    if(G[rmq[dif][poza]]<=G[rmq[dif][pozb-(1<<dif)+1]])
    {
        deepL=G[rmq[dif][poza]];
    }
    else
    {
        deepL=G[rmq[dif][pozb-(1<<dif)+1]];
    }
}

int main()
{
   f>>N>>M>>P;
   for(int i=2;i<=N;i++)
   {
       f>>a>>b;
       V[i].push_back({a,b});
       V[a].push_back({i,b});
   }
   DFS(1,1);
   RMQ();
   COST();
   f>>X>>Y>>A>>B>>C>>D;
   for(int i=1;i<=M;i++)
   {
       if(X!=Y)
       {
           deepA=Level[X];
           deepB=Level[Y];
           LCA(Prim[X],Prim[Y]);
       Z=MAX;
       ans=-(deepL-deepA);
       int deepL1=-(deepL-deepA);
       vertex=X;
       while(ans>0)
       {
           deepL1&=deepL1-1;
           int lg=log2(ans-deepL1);
           Z=min(Z,cost[lg][vertex]);
           vertex=T[lg][vertex];
           ans=deepL1;
       }
       vertex=Y;
       ans=-(deepL-deepB);
       deepL1=-(deepL-deepB);
       while(ans>0)
       {
           deepL1&=deepL1-1;
           int lg=log2(ans-deepL1);
           Z=min(Z,cost[lg][vertex]);
           vertex=T[lg][vertex];
           ans=deepL1;
       }

       }
       else Z=0;

       if(i>=M-P+1) g<<Z<<'\n';
       X1=(A*X+B*Y)%N; X1++;
       Y1=(Y*C+D*Z)%N; Y1++;
       X=X1;
       Y=Y1;
   }
   return 0;
}