Cod sursa(job #1702978)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 15 mai 2016 21:06:43
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int N_MAX = 32001;
const int LOG_MAX = 16;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> graph[N_MAX];
int f[LOG_MAX][N_MAX], c[LOG_MAX][N_MAX], depth[N_MAX];

void Dfs(int crt) {
   depth[crt] = depth[f[0][crt]] + 1;
   for(auto nxt : graph[crt]) {
      if(nxt.first != f[0][crt]) {
         f[0][nxt.first] = crt;
         c[0][nxt.first] = nxt.second;
         Dfs(nxt.first);
      }
   }
}

void Preproc() {
   int i, j;
   
   for(i = 1; i < LOG_MAX; i++) {
      for(j = 1; j < N_MAX; j++) {
         f[i][j] = f[i - 1][f[i - 1][j]];
         c[i][j] = min(c[i - 1][j], c[i - 1][f[i - 1][j]]);
      }
   }
}

int Query(int x, int y) {
   int cost = INF, i, depthDif;
   
   if(depth[x] < depth[y])
      swap(x, y);
   
   depthDif = depth[x] - depth[y];
   for(i = 0; i < LOG_MAX; i++) {
      if(depthDif & (1 << i)) {
         cost = min(cost, c[i][x]);
         x = f[i][x];
      }
   }
   for(i = LOG_MAX - 1; i >= 0; i--) {
      if(f[i][x] != f[i][y]) {
         cost = min(cost, min(c[i][x], c[i][y]));
         x = f[i][x];
         y = f[i][y];
      }
   }
   
   if(x != y)
      cost = min(cost, min(c[0][x], c[0][y]));
   return cost == INF ? 0 : cost;
}

int main() {
   ifstream f("atac.in");
   ofstream g("atac.out");
   
   int N, Q, P, i, j, X, Y, A, B, C, D, Z;
   
   f >> N >> Q >> P;
   
   for(i = 2; i <= N; i++) {
      f >> X >> Y;
      graph[X].push_back(make_pair(i, Y));
      graph[i].push_back(make_pair(X, Y));
   }
   
   for(i = 0; i < LOG_MAX; i++) 
      for(j = 0; j < N_MAX; j++) 
         c[i][j] = INF;
         
   Dfs(1);
   Preproc();
   
   f >> X >> Y >> A >> B >> C >> D;
   for(i = 1; i <= Q; i++) {
      Z = Query(X, Y);
      if(Q - P < i)
         g << Z << '\n';
      X = (int64_t(X) * A + int64_t(Y) * B) % N + 1;
      Y = (int64_t(Y) * C + int64_t(Z) * D) % N + 1;
   }
   
   return 0;
}