Cod sursa(job #1702965)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 15 mai 2016 20:44:27
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

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, int p) {
   depth[crt] = depth[p] + 1;
   for(auto nxt : graph[crt]) {
      if(nxt.first != p) {
         f[0][nxt.first] = crt;
         c[0][nxt.first] = nxt.second;
         Dfs(nxt.first, crt);
      }
   }
}

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(int i = 0; i < LOG_MAX; i++) {
      if(depthDif & (1 << i)) {
         cost = min(cost, c[i][x]);
         x = f[i][x];
      }
   }
   for(int 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];
      }
   }
   
   cost = min(cost, min(c[0][x], c[0][y]));
   if(cost == INF)
      return 0;
   return 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, 0);
   Preproc();
   
   f >> X >> Y >> A >> B >> C >> D;
   for(i = 1; i <= Q; i++) {
      Z = Query(X, Y);
      if(Q - P + 1 <= 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;
}