Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- struct treeNode {
- ll data;
- int left;
- int right;
- };
- //shared_ptr<treeNode> newNode(ll data) {
- // shared_ptr<treeNode> node(new treeNode);
- //
- // node->data = data;
- // node->left = nullptr;
- // node->right = nullptr;
- //
- // return node;
- //}
- //shared_ptr<treeNode> newNode(ll data, int L, int R) {
- // shared_ptr<treeNode> node(new treeNode);
- //
- // node->data = data;
- // node->left = L;
- // node->right = R;
- //
- // return node;
- //}
- //
- //bool find(const shared_ptr<treeNode>& node, ll& x) {
- // if (node == NULL) {
- // return false;
- // }
- // if (node->data == x) {
- // return true;
- // }
- // if (x < node->data) {
- // return find(node->left, x);
- // }
- // else {
- // return find(node->right, x);
- // }
- //}
- //
- //bool inserted;
- //void insertNode(const shared_ptr<treeNode>& current_node, int& v, ll& dataL, ll& dataR) {
- // if (!inserted) {
- // if (current_node == nullptr) {
- // return;
- // }
- // if (current_node->data == v) {
- // if (dataL != -1) {
- // current_node->left = newNode(dataL);
- // }
- // if (dataR != -1) {
- // current_node->right = newNode(dataR);
- // }
- // inserted = true;
- // return;
- // }
- //
- // insertNode(current_node->left, v, dataL, dataR);
- // insertNode(current_node->right, v, dataR, dataR);
- // }
- // else {
- // return;
- // }
- //}
- vector<ll> val;
- vector<pair<int, int>> g;
- vector<bool> vis;
- set<int> finded;
- void dfs(int u, ll& min, ll& max, ll prev = 0, char d = 0) {
- vis[u] = true;
- if (d == 'L') {
- if (val[u] < max && val[u] >= min && val[u] < prev) {
- finded.insert(u);
- }
- }
- if (d == 'R') {
- if (val[u] < max && val[u] >= min && val[u] > prev) {
- finded.insert(u);
- }
- }
- if (g[u].first != -1 && !vis[g[u].first]) {
- dfs(g[u].first, min, max, val[u], 'L');
- }
- if (g[u].first != -1 && !vis[g[u].second]) {
- dfs(g[u].second, min, max, val[u], 'R');
- }
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- int n;
- cin >> n;
- val.resize(n);
- g.resize(n);
- vis.resize(n);
- bool exist[n];
- ll max_val = 0;
- for (int i = 0; i < n; i++) {
- ll v;
- int l, r;
- cin >> v >> l >> r;
- --l, --r;
- max_val = max(max_val, v);
- exist[l] = true;
- exist[r] = true;
- val[i] = v;
- g[i].first = l;
- g[i].second = r;
- }
- int root;
- for (int i = 0; i < n; i++) {
- if (!exist[i]) {
- root = i;
- break;
- }
- }
- ll min = 0, max = val[root];
- vis[g[root].second] = true;
- dfs(root, min, max);
- min = max, max = max_val;
- dfs(root, min, max);
- finded.insert(root);
- cout << n - finded.size() << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement