Cod sursa(job #1954077)

Utilizator TimoteiCopaciu Timotei Timotei Data 5 aprilie 2017 10:34:17
Problema Atac Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
#define nMax 32003
#define logMax 20

using namespace std;
ofstream fout("atac.out");

int n, m, p, A, B, C, D, T[nMax], v[nMax], L[nMax];
typedef struct{
   int nod, mn;
} node;
node dp[nMax][logMax];

void set_values()
{
    for(int j = 0; (1 << j) <= n; ++j)
      for(int i = 1; i <= n; ++i)
        dp[i][j] = {-1, -1};
    for(int i = 2; i <= n; ++i)
      dp[i][0] = {T[i], v[i]};
    for(int j = 1; (1 << j) <= n; ++j)
      for(int i = 2; i <= n; ++i)
        if(dp[i][j - 1].nod != -1){
           dp[i][j].nod = dp[dp[i][j - 1].nod][j - 1].nod;
           dp[i][j].mn = min(dp[i][j - 1].mn, dp[dp[i][j - 1].nod][j - 1].mn);
        }
}
void LCA(int x, int y, int nr)
{
   int X = x, Y = y;
   int minB = (1 << 30);
   if(x == y) minB = 0;
   if(L[x] < L[y]) swap(x, y);
   int step;
   for(step = 0; (1 << step) <= L[x]; ++step);
   --step;
   for(int i = step; i >= 0; --i)
      if(L[x] - (1 << i) >= L[y]){
         minB = min(minB, dp[x][i].mn);
         x = dp[x][i].nod;
      }
   for(int i = step; i >= 0; --i)
     if(dp[x][i].nod != -1 && dp[x][i].nod != dp[y][i].nod){
        minB = min(minB, min(dp[x][i].mn, dp[y][i].mn));
        x = dp[x][i].nod;
        y = dp[y][i].nod;
     }
   if(x != y) minB = min(minB, min(v[x], v[y]));
   if(nr > m - p)
     fout << minB << '\n';
   if(nr < m)
     LCA(((X * A) % n + (Y * B) % n) % n + 1, ((Y * C) % n + (minB * D) % n) % n + 1, nr + 1);

}
void read()
{
    int x, y;
    ifstream fin("atac.in");
    fin >> n >> m >> p;
    for(int i = 2; i <= n; ++i){
        fin >> T[i] >> v[i];
        L[i] = L[T[i]] + 1;
    }
    set_values();
    fin >> x >> y >> A >> B >> C >> D;
    LCA(x, y, 1);
}
int main()
{
    read();
    return 0;
}