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
- vector<ll> val;
- vector<pair<int, int>> g;
- vector<bool> vis;
- unordered_multiset<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].second != -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);
- vector<bool> exist(n);
- ll max_val = 0;
- for (int i = 0; i < n; i++) {
- ll v;
- int l, r;
- cin >> v >> l >> r;
- if (l != -1) {
- --l;
- exist[l] = true;
- }
- if (r != -1) {
- --r;
- exist[r] = true;
- }
- max_val = max(max_val, v);
- 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, max;
- if (g[root].first != -1) {
- min = -1, max = val[root];
- vis[g[root].second] = true;
- dfs(root, min, max);
- }
- if (g[root].second != -1) {
- min = val[root], max = max_val + 1;
- vis[g[root].first] = true;
- vis[g[root].second] = false;
- dfs(root, min, max);
- }
- finded.insert(root);
- cout << n - finded.size() << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement