Cod sursa(job #1938099)

Utilizator edi_laitinLaitin Eduard edi_laitin Data 24 martie 2017 16:57:47
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int N,M,P,E[25][32005],Minedge[25][32005],Log[32005],Sol[500005],nr,X,Y,A,B,C,D,Level[32005],mine;
vector <pair <int,int> > G[32005];

void Read()
{
  fin>>N>>M>>P;
  for(int i=2;i<=N;i++)
  {
     int x,y;
      fin>>x>>y;
      G[x].push_back(make_pair(i,y));
  }
  fin>>X>>Y>>A>>B>>C>>D;

}

void DFS(int Nod)
{

  for(int i = 0; i < (int)G[Nod].size(); ++i)
    {
      int Vecin = G[Nod][i].first;
      int Cost = G[Nod][i].second;
      E[0][Vecin]=Nod;
      Minedge[0][Vecin]=Cost;
      Level[Vecin] = Level[Nod] + 1;
      DFS(Vecin);
    }
}

void Precalculate()
{
    DFS(1);
  for(int i = 2; i <= N; ++i)
    Log[i] = Log[i/2] + 1;

  for(int i = 1; (1<<i) <= N; ++i)
   {
     for(int j = 1; j <= N; ++j)
      {
        E[i][j] = E[i-1][E[i-1][j]];
        Minedge[i][j]=min(Minedge[i-1][j],Minedge[i-1][E[i-1][j]]);
      }
   }
}


int LCA(int x, int y)
{
  if(Level[x] < Level[y])
    swap(x,y);

  while(Level[x]!=Level[y])
   {
     int K = Log[Level[x]-Level[y]];
      x = E[K][x];
   }

  if(x == y)
      return x;

  for(int K = Log[Level[x]]; K >= 0 ; K--)
    {
      if(E[K][x] != E[K][y])
      {
        x = E[K][x];
        y = E[K][y];
      }
    }
  return E[0][x];
}
void findmin(int Nod,int stramos)
{
    while(Nod!=stramos )
    {
        int a=Log[Level[Nod]-Level[stramos]];
        mine=min(mine,Minedge[a][Nod]);
        Nod=E[a][Nod];
    }
}
void Solve()
{
    while(M--)
    {
        mine=2000000000;
        int x1=X,y1=Y;
        if(X==Y)
            {
                mine=0;
            }
        else
        {
            int Nod=LCA(X,Y);
            findmin(X,Nod);
            findmin(Y,Nod);
        }

        Sol[++nr]=mine;
        X =(x1*A + y1*B)%N + 1;
        Y =(y1*C + mine*D)%N + 1;
    }
    for(int i = nr-P+1; i <= nr; i++) fout<<Sol[i]<<'\n';
}

int main()
{
    Read();
    Precalculate();
    Solve();
    return 0;
}