Cod sursa(job #1954118)

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

using namespace std;


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);
        }
}
int LCA(int x, int y)
{
   int minB = (1 << 30);
   if(x == y) return 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]));
   return minB;
}
void read_and_solve()
{
    int x, y, z;
    ifstream fin("atac.in");
    ofstream fout("atac.out");
    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;
    for(int i = 1; i <= m; ++i){
       z = LCA(x, y);
       if(i > m - p)
          fout << z << '\n';
       x = ((x * A) % n + (y * B) % n) % n + 1;
       y = ((y * C) % n + (z * D) % n) % n + 1;
    }
}
int main()
{
    read_and_solve();
    return 0;
}