Cod sursa(job #2188566)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 27 martie 2018 11:20:05
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.3 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int const nmax = 32000;
int const inf = 1000000000;

#define MIN(a , b) ((a < b) ? a : b)

struct Edge{
  int to;
  int cost;
};

vector < Edge > g[5 + nmax];

int level[5 + nmax];//nivelul nodului
int euler[5 + 4 * nmax] , ep = 0;//parcurgere euler
int poseuler[5 + 4 * nmax]; // pozitia nodului in parcurgere

Edge path[20][5 + nmax];


int n;
void build(int node , int levelp , int parent){
  level[node] = levelp;
  for(int h = 0 ; h < g[node].size() ; h++){
    if(g[node][h].to != parent){
      build(g[node][h].to , levelp + 1 , node);
      path[0][g[node][h].to] = {node , g[node][h].cost };
    }
  }
}
void computepaths(){

  path[0][1] = {0 , inf};
  for(int h = 1 ; h < 20 ;h++)
    for(int i = 0 ; i <= n ;i++)
      path[h][i] = {0 , inf};

  path[0][0] = {0 , inf};

  for(int h = 1 ; h < 20 ;h++){
    for(int i = 1 ; i <= n ;i++){
      int jump = path[h - 1][i].to;

      int cost = MIN(path[h - 1][i].cost , path[h - 1][jump].cost);
      path[h][i] = {path[h - 1][jump].to , cost};
    }
  }
}
void geteuler(int node , int parent){
  for(int h = 0 ;h < g[node].size() ;h++){
    if(g[node][h].to != parent){
      geteuler(g[node][h].to ,node);
      euler[++ep] = node;
      poseuler[node] = ep;
    }
  }
  if(g[node].size() == 1){
    euler[++ep] = node;
    poseuler[node] = ep;
  }
}

int lg[5 + 4 * nmax];
int rmq[20][5 + 4 * nmax];

void buildrmq(){
  lg[0] = lg[1] = 0;
  for(int i = 2 ; i <= ep ;i++)
    lg[i] = lg[i / 2] + 1;
  for(int i = 1 ; i <= ep ;i++)
    rmq[0][i] = euler[i];
  for(int h = 1 ; h < 20 ;h++){
    int jump = (1 << (h - 1));
    for(int i = 1 ; i <= ep - (1 << h) + 1 ;i++){
      int a = rmq[h - 1][i];
      int b = rmq[h - 1][i + jump];
      if(level[a] < level[b]){
        rmq[h][i] = a;
      } else
        rmq[h][i] = b;
    }
  }
}

int getlca(int a , int b){
  int x = poseuler[a] , y = poseuler[b];
  if(y < x)
    swap(x , y);

  int dist = lg[y - x];

  int result1 = rmq[dist][x];
  int result2 = rmq[dist][y - (1 << dist) + 1];
  if(level[result1] < level[result2])
    return result1;
  else
    return result2;
}
int getcost(int node , int levels){
  int cost = inf;
  for(int h = 19 ; 0 <= h ;h--){
    if(0 < ((1 << h) & levels)){
      cost = MIN(cost , path[h][node].cost);
      node = path[h][node].to;
    }
  }
  return cost;
}
int solve(int a , int b){
  cout << a << " " << b << '\n';
  int lca = getlca(a , b);
  //cout << level[a] << " " << level[b] << " " <<level[lca] << '\n';
  cout << MIN(getcost(a , level[a] - level[lca]) , getcost(b , level[b] - level[lca] )) << '\n' << '\n';
  return MIN(getcost(a , level[a] - level[lca]) , getcost(b , level[b] - level[lca]));
}

void debug(){
  /*
  cout << "Level :\n";
  for(int i = 1 ; i <= n ;i++)
    cout << level[i] << " " ;
  cout << '\n';
  //*/

  /*
  cout << "Euler : \n";
  for(int i = 1 ; i <= ep ;i++)
    cout << euler[i] << " ";
  cout << '\n';
  //*/

  /*
  cout << "Lca : \n";
  for(int i = 1 ; i <= n ;i++)
    for(int j = i ; j <= n ;j++)
      cout << i << " " << j <<" "<<getlca(i , j) << '\n';
  //*/
  /*
  cout << "Paths :\n";
  for(int h = 0 ; h < 6 ;h++){
    for(int i = 1 ; i <= n ;i++)
      cout << h << " " << i <<" "<<path[h][i].cost <<" " <<path[h][i].to << '\n';
    cout << '\n';
  }
  */
  /*
  cout<< "Costs :\n";
  for(int h = 1 ; h <= 3 ;h++){
    for(int i = 1 ; i <= n ;i++)
      cout << h << " " << i << " " << getcost(i , h) << '\n';
  }
  //*/
}
int main()
{
  int m , p;
  in >> n >> m >> p;
  for(int i = 2 ; i <= n ;i++){
    int a , b;
    in >> a >> b;
    g[i].push_back({a , b});
    g[a].push_back({i , b});
  }
  build(1 , 1 , 0);
  geteuler(1 , 0);
  buildrmq();
  computepaths();
  debug();

  int x , y , a , b , c , d;
  in >> x >> y >> a >> b >> c >> d;
  int result = 0;
  for(int i = 1 ; i <= m ;i++){
    if(i == 1)
      result = solve(x , y);
    else{
      int x2 = (x * a + y * b) % n + 1;
      int y2 = (y * c + result * d) % n + 1;
      result = solve(x2 , y2);
      x = x2;
      y = y2;
    }
    if(m - p + 1 <= i)
      out << result << '\n';
  }
  return 0;
}