leetcode

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

2477.cpp (953B)

      1 class Solution {
      2   public:
      3     long long minimumFuelCost(vector<vector<int>> &roads, int seats) {
      4         int n = roads.size() + 1;
      5         vector<vector<int>> adj(n, vector<int>());
      6         vector<int> count(n, 0);
      7         stack<pair<int, int>> st;
      8 
      9         for (auto &p : roads) {
     10             adj[p[0]].push_back(p[1]);
     11             adj[p[1]].push_back(p[0]);
     12         }
     13 
     14         long long total = 0;
     15         st.push({0, -1});
     16         while (!st.empty()) {
     17             auto [root, parent] = st.top();
     18             st.pop();
     19             if (parent == -2) {
     20                 for (int c : adj[root]) {
     21                     count[root] += count[c];
     22                     total += ceil(1.0 * count[c] / seats);
     23                 }
     24                 count[root]++;
     25                 continue;
     26             }
     27             st.push({root, -2});
     28             for (int c : adj[root])
     29                 if (c != parent) st.push({c, root});
     30         }
     31         return total;
     32     }
     33 };