leetcode

commit f6f1bbdc52b33ced7eb454ab498b777426855135
parent 318897c92a0e546b901a416a8a9d95fa5dabb802
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 20 Jul 2024 13:48:29 +0200

1 Random Problem

Diffstat:
A
Problems/2049.cpp
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 50 insertions(+), 0 deletions(-)
diff --git a/Problems/2049.cpp b/Problems/2049.cpp
@@ -0,0 +1,49 @@
+class Solution {
+  public:
+    int countHighestScoreNodes(const vector<int> &parents) const {
+        const int n = size(parents);
+
+        vector<int> count(n, 0);
+        for (int i = 1; i < n; i++) {
+            count[parents[i]]++;
+        }
+
+        queue<int> q;
+        for (int i = 1; i < n; i++) {
+            if (!count[i]) q.push(i);
+        }
+
+        vector<int> below(n, 1);
+        while (q.front()) {
+            const int root = q.front();
+            q.pop();
+            const int parent = parents[root];
+
+            if (!--count[parent]) q.push(parent);
+            below[parent] += below[root];
+        }
+
+        vector<int> above(n, 0);
+        for (int i = 1; i < n; i++) {
+            above[i] = below[0] - below[i];
+        }
+
+        vector<long long> score(n, 1);
+        for (int i = 1; i < n; i++) {
+            score[parents[i]] *= below[i];
+            score[i] *= above[i];
+        }
+
+        int res = 0;
+        long long maxi = 0;
+        for (const auto n : score) {
+            if (n == maxi) res++;
+            if (n > maxi) {
+                maxi = n;
+                res = 1;
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1050,6 +1050,7 @@ for solving problems.
 |  2039  |   Medium   | [The Time When the Network Becomes Idle](Problems/2039.cpp)                                        |
 |  2043  |   Medium   | [Simple Bank System](Problems/2043.cpp)                                                            |
 |  2044  |   Medium   | [Count Number of Maximum Bitwise-OR Subsets](Problems/2044.cpp)                                    |
+|  2049  |   Medium   | [Count Nodes With the Highest Score](Problems/2049.cpp)                                            |
 |  2050  |    Hard    | [Parallel Courses III](Problems/2050.cpp)                                                          |
 |  2058  |   Medium   | [Find the Minimum and Maximum Number of Nodes Between Critical Points](Problems/2058.cpp)          |
 |  2063  |   Medium   | [Vowels of All Substrings](Problems/2063.cpp)                                                      |