leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2467.cpp (1950B)

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