Advertisement
Art_Uspen

Untitled

May 30th, 2021
644
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 2'100'000'000;
  5.  
  6. void
  7. count_heights(int now, vector<std::vector<int>> &m_adj, vector<bool> &visited,
  8.              vector<int> &heights, vector<int> &ancestors) {
  9.    visited[now] = true;
  10.    if (now == 0) {
  11.        heights[now] = 0;
  12.    } else {
  13.        heights[now] = heights[ancestors[now]] + 1;
  14.    }
  15.    for (auto neig : m_adj[now]) {
  16.        if (!visited[neig]) {
  17.            count_heights(neig, m_adj, visited, heights, ancestors);
  18.        }
  19.    }
  20. }
  21.  
  22. void balance_h(int &v_first, int &v_second, const vector<int> &heights, const vector<int> &ancestors) {
  23.    if (heights[v_first] == heights[v_second]) {
  24.        return;
  25.    }
  26.    if (heights[v_first] > heights[v_second]) {
  27.        while (heights[v_first] != heights[v_second]) {
  28.            v_first = ancestors[v_first];
  29.        }
  30.    } else {
  31.        balance_h(v_second, v_first, heights, ancestors);
  32.    }
  33.  
  34. }
  35.  
  36. int LCA(int v_first, int v_second,
  37.        vector<vector<int>> &up,
  38.        const vector<int> &ancestors,vector<int>&heights) {
  39.    balance_h(v_first, v_second,heights,ancestors);
  40.    if (v_first == v_second) {
  41.        return v_first;
  42.    }
  43.    int k = up.size() - 1;
  44.    while (k >= 0) {
  45.        if (up[k][v_first] != up[k][v_second]) {
  46.            v_first = up[k][v_first];
  47.            v_second = up[k][v_second];
  48.        }
  49.        --k;
  50.    }
  51.    if (v_first == v_second) {
  52.        return v_first;
  53.    }
  54.    return ancestors[v_first];
  55. }
  56.  
  57. int main() {
  58.    int N, M;
  59.    cin >> N >> M;
  60.    vector<int> arr(N);
  61.    vector<int> ancestors(N, -1);
  62.    ancestors[0] = -1;
  63.    vector<vector<int>> m_adj;
  64.    m_adj.resize(N);
  65.    vector<bool> visited(N, false);
  66.    for (int i = 1; i < N; ++i) {
  67.        cin >> arr[i];
  68.        ancestors[i] = arr[i];
  69.        m_adj[arr[i]].push_back(i);
  70.        m_adj[i].push_back(arr[i]);
  71.    }
  72.    vector<int> heights(N);
  73.    count_heights(0, m_adj, visited, heights, ancestors);
  74.    int max_degree = 0;
  75.    while (pow(2, max_degree + 1) < N) {
  76.        ++max_degree;
  77.    }
  78.    vector<vector<int>> up(max_degree + 1, vector<int>(N, 0));
  79.    up[0][0] = -1;
  80.    for (int el = 1; el < N; ++el) {
  81.        up[0][el] = ancestors[el];
  82.    }
  83.    for (int i = 1; i <= max_degree; ++i) {
  84.        for (int el = 1; el < N; ++el) {
  85.            if (up[i - 1][el] == -1) {
  86.                up[i][el] = -1;
  87.            } else {
  88.                up[i][el] = up[i - 1][up[i - 1][el]];
  89.            }
  90.        }
  91.    }
  92.    int a_first, a_second;
  93.    cin >> a_first >> a_second;
  94.    int x, y, z;
  95.    cin >> x >> y >> z;
  96.    int sum_ = 0;
  97.    int a_third = a_first;
  98.    int a_fouth = a_second;
  99. //    balance_h(a_third, a_fouth, heights, ancestors);
  100.    int last_ans = LCA(a_third, a_fouth, up, ancestors,heights);
  101.    sum_ += last_ans;
  102.    for (int i = 2; i <= M; ++i) {
  103.        a_first = (x * a_third + y * a_fouth + z) % N;
  104.        a_second = (x * a_fouth + y * a_first + z) % N;
  105.        a_third = a_first;
  106.        a_fouth = a_second;
  107. //        balance_h(query_first, query_second, heights, ancestors);
  108.        last_ans = LCA((a_first + last_ans) % N, a_second, up, ancestors,heights);
  109.        sum_ += last_ans;
  110.    }
  111.    cout << sum_;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement