leetcode

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

2467.cpp (1950B)

      1 class Solution {
      2     vector<vector<int>> adj;
      3     vector<bool> visited;
      4     vector<int> distance, parent;
      5 
      6     void distance_parent(int start) {
      7         stack<pair<int, int>> st;
      8         st.push({start, 0});
      9         parent[start] = 0;
     10         while (!st.empty()) {
     11             int p = st.top().first;
     12             int d = st.top().second;
     13             st.pop();
     14             distance[p] = d;
     15             for (int c : adj[p])
     16                 if (distance[c] == -1) {
     17                     parent[c] = p;
     18                     st.push({c, d + 1});
     19                 }
     20         }
     21     }
     22 
     23     int profit(int start, vector<int> &amount) {
     24         stack<pair<int, int>> st;
     25         st.push({start, 0});
     26 
     27         int maxi = INT_MIN;
     28         while (!st.empty()) {
     29             int count = 0;
     30             int root = st.top().first;
     31             int value = st.top().second + amount[root];
     32             st.pop();
     33 
     34             visited[root] = true;
     35             for (int c : adj[root])
     36                 if (!visited[c]) {
     37                     count++;
     38                     st.push({c, value});
     39                 }
     40             if (!count) maxi = max(value, maxi);
     41         }
     42 
     43         return maxi;
     44     }
     45 
     46   public:
     47     int mostProfitablePath(vector<vector<int>> &edges, int bob, vector<int> &amount) {
     48         int size = amount.size();
     49         adj.resize(size, vector<int>());
     50         distance.resize(size, -1);
     51         parent.resize(size, -1);
     52         visited.resize(size, false);
     53 
     54         for (auto &e : edges) {
     55             adj[e[0]].push_back(e[1]);
     56             adj[e[1]].push_back(e[0]);
     57         }
     58 
     59         distance_parent(0);
     60 
     61         for (int current = bob, bob_distance = 0; current; bob_distance++) {
     62             if (distance[current] > bob_distance)
     63                 amount[current] = 0;
     64             else if (distance[current] == bob_distance)
     65                 amount[current] /= 2;
     66             current = parent[current];
     67         }
     68 
     69         return profit(0, amount);
     70     }
     71 };