Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define forn(i, n) for (int i = 0; i < n; ++i)
  6. #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  7. #define pb push_back
  8.  
  9. const int N = 100010;
  10. const int INF = 1000000000;
  11.  
  12. typedef long long ll;
  13.  
  14. int tin[N], tout[N];
  15. vector<int> g[N];
  16. int d[N];
  17. vector<int> ord;
  18. int first[N];
  19. int sp[20][N];
  20. int lg[2 * N];
  21.  
  22. void dfs(int v)
  23. {
  24.     first[v] = ord.size();
  25.     ord.pb(v);
  26.     for (int to: g[v])
  27.     {
  28.         d[to] = d[v] + 1;
  29.         dfs(to);
  30.         ord.pb(v);
  31.     }
  32. }
  33.  
  34. int getMin(int a, int b)
  35. {
  36.     if (a > b)
  37.         swap(a, b);
  38.     int len = b - a + 1;
  39.     int k = lg[len];
  40.     int ans = sp[k][b - (1 << k) + 1];
  41.     if (d[ans] > d[sp[k][a]])
  42.         ans = d[sp[k][a]];
  43.     return ans;
  44. }
  45.  
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(0);
  49.     cin.tie(false);
  50.     cout.tie(false);
  51.     lg[1] = 0;
  52.     for (int i = 2, e = 2 * N; i < e; ++i)
  53.         lg[i] = lg[i >> 1] + 1;
  54.     int n, m;
  55.     cin >> n >> m;
  56.     for (int i = 1; i < n; ++i)
  57.     {
  58.         int p;
  59.         cin >> p;
  60.         g[p].pb(i);
  61.     }
  62.     dfs(0);
  63.     forn (i, ord.size())
  64.         sp[0][i] = ord[i];
  65.     for (int i = 1; i <= lg[ord.size()]; ++i)
  66.         for (int j = 0; j + (1 << (i - 1)) < ord.size(); ++j)
  67.         {
  68.             sp[i][j] = sp[i - 1][j + (1 << (i - 1))];
  69.             if (d[sp[i][j]] > d[sp[i - 1][j]])
  70.                 d[sp[i][j]] = d[sp[i - 1][j]];
  71.         }
  72.     int a, b, x, y, z;
  73.     cin >> a >> b >> x >> y >> z;
  74.     ll res = 0;
  75.     forn (i, m)
  76.     {
  77.         int v = getMin(first[a], first[b]);
  78.         res += v;
  79.         a = (x * a + y * b + z) % n;
  80.         b = (x * b + y * a + z) % n;
  81.         a = (a + v) % n;
  82.     }
  83.     cout << res;
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement