leetcode

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

2039.cpp (867B)

      1 class Solution {
      2   public:
      3     int networkBecomesIdle(vector<vector<int>> &edges, vector<int> &patience) {
      4         const int n = patience.size();
      5         vector<vector<int>> adj(n, vector<int>());
      6 
      7         for (auto &p : edges) {
      8             adj[p[0]].push_back(p[1]);
      9             adj[p[1]].push_back(p[0]);
     10         }
     11 
     12         const int master = 0;
     13         int time = 0;
     14         vector<int> dist(n, 0);
     15         queue<int> q;
     16         q.push(0);
     17         while (!q.empty()) {
     18             int root = q.front();
     19             q.pop();
     20             for (int c : adj[root]) {
     21                 if (!dist[c] && c != master) {
     22                     dist[c] = dist[root] + 1;
     23                     time = max(time, ((2 * dist[c] - 1) / patience[c]) * patience[c] + 2 * dist[c]);
     24                     q.push(c);
     25                 }
     26             }
     27         }
     28         return time + 1;
     29     }
     30 };