Advertisement
Galebickosikasa

Untitled

Oct 14th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.00 KB | None | 0 0
  1. #pragma GCC target("avx,avx2")
  2. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
  4. #pragma GCC optimize("03")
  5.  
  6. #include <iostream>
  7. #include <vector>
  8. #include <cmath>
  9. #include <numeric>
  10. #include <algorithm>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. #include <set>
  14. #include <map>
  15. #include <queue>
  16. #include <deque>
  17. #include <bitset>
  18. #include <stack>
  19. #include <random>
  20.  
  21. #define pb push_back
  22. #define ll long long
  23. #define ld long double
  24. #define all(a) a.begin(), a.end()
  25. #define sz(a) (int)a.size()
  26.  
  27. using namespace std;
  28.  
  29. //tg: @galebickosikasa
  30.  
  31. const int maxn = (int)3e5;
  32. const int inf = (int)2e9;
  33. const ld eps = 1e-9;
  34. mt19937 SuperRandom;
  35.  
  36. vector<pair<int, int>> order;
  37. vector<int> d, first_icon;
  38.  
  39. struct SparseTable{
  40. vector<vector<pair<int, int>>> st;
  41. vector<int> pow;
  42.  
  43. SparseTable(){
  44. int j = 1;
  45. while (1<<j < sz(order)) ++j;
  46. st = vector<vector<pair<int, int>>> (j, vector<pair<int, int>> (sz(order)));
  47. pow = vector<int> (sz(order) + 1);
  48. int tmp = 0;
  49. for (int i = 0; i < sz(order); ++i){
  50. st[0][i] = order[i];
  51. if (1<<(tmp + 1) <= i) ++tmp;
  52. pow[i] = tmp;
  53. }
  54. pow[sz(order)] = j - 1;
  55. for (int k = 1; k < j; ++k){
  56. for (int i = 0; i < sz(order); ++i){
  57. st[k][i] = min(st[k - 1][i], st[k - 1][i + (1<<(k - 1))]);
  58. }
  59. }
  60. }
  61.  
  62. int get(int l, int r) const {
  63. if (l > r) swap(l, r);
  64. int k = pow[r - l + 1];
  65. return min(st[k][l], st[k][r - (1<<k) + 1]).second;
  66. }
  67.  
  68. };
  69.  
  70. int lca(int v, int u, const SparseTable& t){
  71. return t.get(first_icon[u], first_icon[v]);
  72. }
  73.  
  74. void dfs(int v, vector<int>& used, const vector<vector<int>>& G, int deaph = 0){
  75. order.pb({deaph, v});
  76. d[v] = deaph;
  77. used[v] = 1;
  78. for (auto& u: G[v]){
  79. if (used[u]) continue;
  80. dfs(u, used, G, deaph + 1);
  81. order.pb({deaph, v});
  82. }
  83. }
  84.  
  85. void kek(const SparseTable& goo, const vector<vector<int>>& G){
  86. int max_ans = 1, v = 1;
  87. cout << 1 << '\n';
  88. for (int i = 2; i < sz(G); ++i){
  89. int dist = d[i] + d[v] - d[lca(i, v, goo)];
  90. if (d[i] > d[v]){
  91. v = i;
  92. }
  93. if (dist > max_ans){
  94. max_ans = dist;
  95. if (d[i] > )
  96. }
  97.  
  98. }
  99. }
  100.  
  101. int main(){
  102. ios_base::sync_with_stdio(false);
  103. cout.tie(nullptr);
  104. cin.tie(nullptr);
  105. int n;
  106. cin >> n;
  107. vector<vector<int>> G(n);
  108. for (int i = 0; i < n; ++i){
  109. int v;
  110. cin >> v;
  111. if (i == 0) continue;
  112. --v;
  113. G[v].pb(i), G[i].pb(v);
  114. }
  115. vector<int> used(n, 0);
  116. d = vector<int> (n);
  117. first_icon = vector<int> (n, -1);
  118. for (int i = 0; i < sz(order); ++i)
  119. if (first_icon[order[i].second] == -1)
  120. first_icon[order[i].second] = i;
  121. dfs(0, used, G);
  122. SparseTable goo;
  123.  
  124.  
  125.  
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement