leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2049.cpp (1172B)

      1 class Solution {
      2   public:
      3     int countHighestScoreNodes(const vector<int> &parents) const {
      4         const int n = size(parents);
      5 
      6         vector<int> count(n, 0);
      7         for (int i = 1; i < n; i++) {
      8             count[parents[i]]++;
      9         }
     10 
     11         queue<int> q;
     12         for (int i = 1; i < n; i++) {
     13             if (!count[i]) q.push(i);
     14         }
     15 
     16         vector<int> below(n, 1);
     17         while (q.front()) {
     18             const int root = q.front();
     19             q.pop();
     20             const int parent = parents[root];
     21 
     22             if (!--count[parent]) q.push(parent);
     23             below[parent] += below[root];
     24         }
     25 
     26         vector<int> above(n, 0);
     27         for (int i = 1; i < n; i++) {
     28             above[i] = below[0] - below[i];
     29         }
     30 
     31         vector<long long> score(n, 1);
     32         for (int i = 1; i < n; i++) {
     33             score[parents[i]] *= below[i];
     34             score[i] *= above[i];
     35         }
     36 
     37         int res = 0;
     38         long long maxi = 0;
     39         for (const auto n : score) {
     40             if (n == maxi) res++;
     41             if (n > maxi) {
     42                 maxi = n;
     43                 res = 1;
     44             }
     45         }
     46 
     47         return res;
     48     }
     49 };