Advertisement
he_obviously

Untitled

Jul 17th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.22 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("O3")
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <cmath>
  9. //#include <ext/pb_ds/assoc_container.hpp>
  10. //include <ext/pb_ds/tree_policy.hpp>
  11.  
  12. using namespace std;
  13. //using namespace __gnu_pbds;
  14.  
  15. typedef long long ll;
  16. typedef long double ld;
  17.  
  18. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  19. #define all(x) (x).begin(),(x).end()
  20. #define pii pair<int, int>
  21. #define sz(x) (int)x.size()
  22.  
  23. vector<vector<int>> v;
  24. vector<int> order, first, h, tree;
  25. vector<bool> used;
  26.  
  27. void dfs(int i, int _h) {
  28.     used[i] = 1;
  29.     h[i] = _h;
  30.     order.push_back(i);
  31.     for (int x : v[i]) {
  32.         if (!used[x]) {
  33.             dfs(x, _h + 1);
  34.             order.push_back(i);
  35.         }
  36.     }
  37. }
  38.  
  39. void build(int v, int tl, int tr) {
  40.     if (tr - tl == 1) {
  41.         tree[v] = order[tl];
  42.     }
  43.     else {
  44.         int tm = (tl + tr) / 2;
  45.         build(2 * v + 1, tl, tm);
  46.         build(2 * v + 2, tm, tr);
  47.         if (h[tree[2 * v + 1]] < h[tree[2 * v + 2]]) {
  48.             tree[v] = tree[2 * v + 1];
  49.         }
  50.         else {
  51.             tree[v] = tree[2 * v + 2];
  52.         }
  53.     }
  54. }
  55.  
  56. int get(int v, int tl, int tr, int l, int r) {
  57.     if (tl >= l && tr <= r) {
  58.         return tree[v];
  59.     }
  60.     int tm = (tl + tr) / 2;
  61.     if (r <= tm) {
  62.         return get(2 * v + 1, tl, tm, l, r);
  63.     }
  64.     else if (l >= tm) {
  65.         return get(2 * v + 2, tm, tr, l, r);
  66.     }
  67.     else {
  68.         int ans1 = get(2 * v + 1, tl, tm, l, tm);
  69.         int ans2 = get(2 * v + 2, tm, tr, tm, r);
  70.         return (h[ans1] < h[ans2] ? ans1 : ans2);
  71.     }
  72. }
  73.  
  74. int lca(int a, int b) {
  75.     int left = first[a], right = first[b];
  76.     if (left > right) swap(left, right);
  77.     return get(0, 0, sz(order), left, right + 1);
  78. }
  79.  
  80. int main() {
  81.  
  82.     ios_base::sync_with_stdio(0);
  83.     cin.tie(0); cout.tie(0);
  84.  
  85.     int n, m;
  86.     cin >> n >> m;
  87.  
  88.     v.resize(n);
  89.     first.resize(n, -1);
  90.     h.resize(n);
  91.     used.resize(n, 0);
  92.  
  93.     for (int i = 1; i <= n - 1; ++i) {
  94.         int x; cin >> x;
  95.         v[i].push_back(x);
  96.         v[x].push_back(i);
  97.     }
  98.  
  99.     dfs(0, 0);
  100.  
  101.     tree.resize(8 * sz(order));
  102.  
  103.     build(0, 0, sz(order));
  104.  
  105.     for (int i = 0; i < sz(order); ++i) {
  106.         if (first[order[i]] == -1) {
  107.             first[order[i]] = i;
  108.         }
  109.     }
  110.  
  111.     long long x, y, z;
  112.     vector<int> a(2 * m + 4);
  113.  
  114.     cin >> a[1] >> a[2] >> x >> y >> z;
  115.  
  116.     long long ans = 0;
  117.     int v;
  118.  
  119.     for (int i = 1; i <= 2 * m - 1; i += 2) {
  120.         if (i == 1) {
  121.             //cout << a[i] << " " << a[i + 1] << " " << lca(a[i], a[i + 1]) << "\n";
  122.             v = lca(a[i], a[i + 1]);
  123.         }
  124.         else {
  125.             //cout << (a[i] + v) % n << " " << a[i + 1] << " " << lca((a[i] + v) % n, a[i + 1]) << "\n";
  126.             v = lca((a[i] + v) % n, a[i + 1]);
  127.         }
  128.         ans += v;
  129.         a[i + 2] = (int)((x * (long long)(a[i]) + y * (long long)(a[i + 1]) + z) % (long long)(n));
  130.         a[i + 3] = (int)((x * (long long)(a[i + 1]) + y * (long long)(a[i + 2]) + z) % (long long)(n));
  131.     }
  132.  
  133.     cout << ans;
  134.  
  135.     return 0;
  136.  
  137. }
  138.  
  139. /*
  140. 7 8
  141. 0 1 1 1 0 5
  142. 6 3
  143. 1 1 1
  144. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement