leetcode

Solution to some Leetcode problems written in C++

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

2039.cpp (867B)

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