Advertisement
TwITe

Untitled

Jan 24th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ull unsigned long long
  6.  
  7. struct treeNode {
  8.     ll data;
  9.     int left;
  10.     int right;
  11. };
  12.  
  13. //shared_ptr<treeNode> newNode(ll data) {
  14. //    shared_ptr<treeNode> node(new treeNode);
  15. //
  16. //    node->data = data;
  17. //    node->left = nullptr;
  18. //    node->right = nullptr;
  19. //
  20. //    return node;
  21. //}
  22.  
  23. //shared_ptr<treeNode> newNode(ll data, int L, int R) {
  24. //    shared_ptr<treeNode> node(new treeNode);
  25. //
  26. //    node->data = data;
  27. //    node->left = L;
  28. //    node->right = R;
  29. //
  30. //    return node;
  31. //}
  32. //
  33. //bool find(const shared_ptr<treeNode>& node, ll& x) {
  34. //    if (node == NULL) {
  35. //        return false;
  36. //    }
  37. //    if (node->data == x) {
  38. //        return true;
  39. //    }
  40. //    if (x < node->data) {
  41. //        return find(node->left, x);
  42. //    }
  43. //    else {
  44. //        return find(node->right, x);
  45. //    }
  46. //}
  47. //
  48. //bool inserted;
  49. //void insertNode(const shared_ptr<treeNode>& current_node, int& v, ll& dataL, ll& dataR) {
  50. //    if (!inserted) {
  51. //        if (current_node == nullptr) {
  52. //            return;
  53. //        }
  54. //        if (current_node->data == v) {
  55. //            if (dataL != -1) {
  56. //                current_node->left = newNode(dataL);
  57. //            }
  58. //            if (dataR != -1) {
  59. //                current_node->right = newNode(dataR);
  60. //            }
  61. //            inserted = true;
  62. //            return;
  63. //        }
  64. //
  65. //        insertNode(current_node->left, v, dataL, dataR);
  66. //        insertNode(current_node->right, v, dataR, dataR);
  67. //    }
  68. //    else {
  69. //        return;
  70. //    }
  71. //}
  72.  
  73. vector<ll> val;
  74. vector<pair<int, int>> g;
  75. vector<bool> vis;
  76. set<int> finded;
  77.  
  78.  
  79. void dfs(int u, ll& min, ll& max, ll prev = 0, char d = 0) {
  80.     vis[u] = true;
  81.  
  82.     if (d == 'L') {
  83.         if (val[u] < max && val[u] >= min && val[u] < prev) {
  84.             finded.insert(u);
  85.         }
  86.     }
  87.     if (d == 'R') {
  88.         if (val[u] < max && val[u] >= min && val[u] > prev) {
  89.             finded.insert(u);
  90.         }
  91.     }
  92.  
  93.     if (g[u].first != -1 && !vis[g[u].first]) {
  94.         dfs(g[u].first, min, max, val[u], 'L');
  95.     }
  96.     if (g[u].first != -1 && !vis[g[u].second]) {
  97.         dfs(g[u].second, min, max, val[u], 'R');
  98.     }
  99. }
  100.  
  101. int main() {
  102.     ios::sync_with_stdio(false);
  103.     cin.tie(NULL);
  104.  
  105.     int n;
  106.     cin >> n;
  107.  
  108.     val.resize(n);
  109.     g.resize(n);
  110.     vis.resize(n);
  111.  
  112.     bool exist[n];
  113.  
  114.     ll max_val = 0;
  115.  
  116.     for (int i = 0; i < n; i++) {
  117.         ll v;
  118.         int l, r;
  119.         cin >> v >> l >> r;
  120.         --l, --r;
  121.  
  122.         max_val = max(max_val, v);
  123.  
  124.         exist[l] = true;
  125.         exist[r] = true;
  126.  
  127.         val[i] = v;
  128.         g[i].first = l;
  129.         g[i].second = r;
  130.     }
  131.  
  132.     int root;
  133.  
  134.     for (int i = 0; i < n; i++) {
  135.         if (!exist[i]) {
  136.             root = i;
  137.             break;
  138.         }
  139.     }
  140.  
  141.     ll min = 0, max = val[root];
  142.     vis[g[root].second] = true;
  143.     dfs(root, min, max);
  144.  
  145.     min = max, max = max_val;
  146.     dfs(root, min, max);
  147.  
  148.     finded.insert(root);
  149.  
  150.     cout << n - finded.size() << endl;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement