Cod sursa(job #2409358)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 18 aprilie 2019 22:23:51
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <bits/stdc++.h>
#define Dim 32007
#define MAX 100006
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;
int rmq[16][Dim],Deep[Dim],Cont[Dim],maxim;
int vertex,low_scad,Cost[Dim],bazaA,bazaB;
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;
    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])
        {
            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 DFS2(int nod)
{
    viz2[nod]=1;
    maxim++;
    Cont[nod]=maxim;
    for(unsigned int i=0;i<V[nod].size();i++)
    {
        int vecin=V[nod][i].first;
        if(!viz2[vecin]) DFS2(vecin);
    }
}

void BFS()
{
    queue < pi > qu;
    viz3[1]=0;
    Deep[1]=1;
    qu.push({1,1});
    S[1].insert({1,1});
    while(!qu.empty())
    {
        int nod=qu.front().first;
        int niv=qu.front().second+1;
        qu.pop();
        viz3[nod]=1;
        for(unsigned int i=0;i<V[nod].size();i++)
        {
            int vecin=V[nod][i].first;
            if(!viz3[vecin])
            {
                viz3[vecin]=1;
                Deep[vecin]=niv;
                S[niv].insert({Cont[vecin],vecin});
                qu.push({vecin,niv});
            }
        }
    }
}

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});
       Cost[i]=b;
   }
   DFS(1,1);
   RMQ();
   DFS2(1);
   BFS();
   //for(int i=1;i<=N;i++) cout<<i<<" "<<Cost[i]<<'\n';
   f>>X>>Y>>A>>B>>C>>D;
   for(int i=1;i<=M;i++)
   {
      a=Prim[X]; b=Prim[Y];
      if(a>b) swap(a,b);

      int lg=log2(b-a+1);
      int poza=rmq[lg][a];
      int pozb=rmq[lg][b-(1<<lg)+1];

      if(G[poza]<=G[pozb]) vertex=E[poza];
      else vertex=E[pozb];

      bazaA=X; bazaB=Y;
      if(bazaA!=bazaB)
      {
          int limit=Deep[X]-Deep[vertex];
      int recent=X;
      Z=MAX;
//if(i==1) cout<<X<<" "<<Deep[X]<<" "<<vertex<<" "<<Deep[vertex]<<" "<<limit<<'\n';
      for(int j=1;j<=limit;j++)
      {
          Z=min(Z,Cost[X]);
                  //if(i==1) cout<<X<<" "<<bazaA<<" "<<bazaB<<" "<<Cost[X]<<'\n';
          int level=Deep[recent]-1;
          int ID=Cont[recent];
          //it=S[level].lower_bound({ID,level});
          //it--;
          //X=it->second;

          recent=X;
          //if(i==2) cout<<j<<" "<<limit<<'\n';
      }
//cout<<i<<" "<<X<<" "<<Y<<'\n';
      limit=Deep[Y]-Deep[vertex];
      recent=Y;
      X=Y;
      for(int j=1;j<=limit;j++)
      {//cout<<i<<" "<<vertex<<" "<<j<<" "<<recent<<" "<<X<<" "<<limit<<'\n';
          Z=min(Z,Cost[X]);
          //if(i==1) cout<<X<<" "<<bazaA<<" "<<bazaB<<" "<<Cost[X]<<'\n';
          int level=Deep[recent]-1;
          int ID=Cont[recent];
          //it=S[level].lower_bound({ID,0});
         // it--;
          //X=it->second;

          recent=X;

      }

      }
      else Z=0;

      if(i>=M-P+1) g<<Z<<'\n';

      X1=(bazaA*A+bazaB*B)%N; X1++;
      Y1=(C*bazaB+Z*D)%N; Y1++;
      X=X1;
      Y=Y1;
      //cout<<i<<" "<<bazaA<<" "<<bazaB<<" "<<X<<" "<<Y<<" "<<Z<<'\n';
      // cout<<bazaA<<" "<<bazaB<<" "<<X<<" "<<Y<<" "<<Z<<'\n';
   }
   return 0;
}