Advertisement
TwITe

Untitled

Jan 24th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 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. vector<ll> val;
  8. vector<pair<int, int>> g;
  9. vector<bool> vis;
  10. unordered_multiset<int> finded;
  11.  
  12. void dfs(int u, ll& min, ll& max, ll prev = 0, char d = 0) {
  13.     vis[u] = true;
  14.  
  15.     if (d == 'L') {
  16.         if (val[u] < max && val[u] > min && val[u] < prev) {
  17.             finded.insert(u);
  18.         }
  19.     }
  20.     if (d == 'R') {
  21.         if (val[u] < max && val[u] > min && val[u] > prev) {
  22.             finded.insert(u);
  23.         }
  24.     }
  25.  
  26.     if (g[u].first != -1 && !vis[g[u].first]) {
  27.         dfs(g[u].first, min, max, val[u], 'L');
  28.     }
  29.     if (g[u].second != -1 && !vis[g[u].second]) {
  30.         dfs(g[u].second, min, max, val[u], 'R');
  31.     }
  32. }
  33.  
  34. int main() {
  35.     ios::sync_with_stdio(false);
  36.     cin.tie(NULL);
  37.  
  38.     int n;
  39.     cin >> n;
  40.  
  41.     val.resize(n);
  42.     g.resize(n);
  43.     vis.resize(n);
  44.     vector<bool> exist(n);
  45.  
  46.     ll max_val = 0;
  47.  
  48.     for (int i = 0; i < n; i++) {
  49.         ll v;
  50.         int l, r;
  51.         cin >> v >> l >> r;
  52.         if (l != -1) {
  53.             --l;
  54.             exist[l] = true;
  55.         }
  56.         if (r != -1) {
  57.             --r;
  58.             exist[r] = true;
  59.         }
  60.  
  61.         max_val = max(max_val, v);
  62.  
  63.         val[i] = v;
  64.         g[i].first = l;
  65.         g[i].second = r;
  66.     }
  67.  
  68.     int root;
  69.     for (int i = 0; i < n; i++) {
  70.         if (!exist[i]) {
  71.             root = i;
  72.             break;
  73.         }
  74.     }
  75.  
  76.     ll min, max;
  77.     if (g[root].first != -1) {
  78.         min = -1, max = val[root];
  79.         vis[g[root].second] = true;
  80.         dfs(root, min, max);
  81.     }
  82.  
  83.     if (g[root].second != -1) {
  84.         min = val[root], max = max_val + 1;
  85.         vis[g[root].first] = true;
  86.         vis[g[root].second] = false;
  87.         dfs(root, min, max);
  88.     }
  89.  
  90.     finded.insert(root);
  91.  
  92.     cout << n - finded.size() << endl;
  93.  
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement