Advertisement
Art_Uspen

Untitled

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