Cod sursa(job #2677806)

Utilizator euyoTukanul euyo Data 27 noiembrie 2020 15:59:46
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int MaxM = 500001;
const int MaxN = 32002;
const int MaxLog = 16;

struct edge {
  int node, cost;
};

vector<edge> G[MaxN];
int anc[MaxN][MaxLog];
int mn[MaxN][MaxLog];
int log[MaxN];
int level[MaxN], vis[MaxN];

void DFS( int node ) {
  vis[node] = 1;
  for ( int i = 0; i < (int)G[node].size(); ++i ) {
	if ( !vis[G[node][i].node] ) {
	  level[G[node][i].node] = level[node] + 1; //actualizam nivelul
	  anc[G[node][i].node][0] = node; //parintele lui G[node][i].node este node
      mn[G[node][i].node][0] = G[node][i].cost; //minimul este chiar costul muchiei dintre ei
	  DFS( G[node][i].node ); //ne extindem la urmatorul
	}  
  }
}

int query( int x, int y ) {
  int sol = 1e9, lg;
  
  if ( level[x] < level[y] ) { //vrem ca level[x] > level[y] pentru a evita if-uri
	swap( x, y );
  }
  while ( level[x] != level[y] ) { 
	lg = log[level[x] - level[y]]; //luam puterea maxima de 2 care intra in diferenta de nivel
	sol = min( sol, mn[x][lg] ); //actualizam si minimul
	x = anc[x][lg]; //x va deveni stramosul 2^lg al lui 
  }
  lg = MaxLog - 1;
  while ( x != y ) {
	while ( lg && anc[x][lg] == anc[y][lg] ) {
      lg >>= 1;
	}
	sol = min({ sol, mn[x][lg], mn[y][lg] });
	x = anc[x][lg];
	y = anc[y][lg];
  }
  if ( sol == 1e9 ) {
	sol = 0;
  }
  return sol;
}

int q[MaxM];

int main() {
  int n, m, p, x, y, a, b, c, d, res, r;
  edge e;
  
  fin >> n >> m >> p;
  for ( int i = 2; i <= n; ++i ) {
    fin >> e.node >> e.cost;
    G[i].push_back( e );
	G[e.node].push_back( { i, e.cost } );
  }
  level[1] = 0;
  DFS( 1 );
  for ( int k = 1; k <= MaxLog - 1; ++k ) {
    for	( int i = 1; i <= n; ++i ) {
      anc[i][k] = anc[anc[i][k - 1]][k - 1];
	  mn[i][k] = min( mn[i][k - 1], mn[anc[i][k - 1]][k - 1] );
	}
  }
  for ( int i = 2; i <= n; ++i ) {
	log[i] = log[i / 2] + 1;
  }
  fin >> x >> y >> a >> b >> c >> d;
  r = 0;
  for ( int i = 0; i < m; ++i ) {
	res = query( x, y );
    q[r++] = res;
	x = (x * a + y * b) % n + 1;
	y = (y * c + res * d) % n + 1;
  }
  for ( int i = r - p; i < r; ++i ) {
	fout << q[i] << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}