leetcode

commit 5a2766461d2ac2761e311719d3a4a15f679af1f6
parent 388237bfd46c38da32d109a9222cd3a2a6e7a080
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat,  3 Jun 2023 14:17:05 +0200

Daily Problem

Diffstat:
A
Problems/1376.cpp
 | 
26
++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 27 insertions(+), 0 deletions(-)
diff --git a/Problems/1376.cpp b/Problems/1376.cpp
@@ -0,0 +1,26 @@
+class Solution {
+public:
+  int numOfMinutes(int n, int headID, const vector<int> &manager,
+                   const vector<int> &informTime) {
+    vector<int> time(n, -1);
+    time[headID] = 0;
+    int res = 0, crnt, sum1, sum2;
+    for (int i = 0; i < n; i++) {
+      if (informTime[i] != 0) continue;
+      crnt = i, sum1 = 0;
+      while (time[crnt] == -1) {
+        sum1 += informTime[crnt];
+        crnt = manager[crnt];
+      }
+      res = max(res, sum1 += time[crnt]);
+      crnt = i, sum2 = 0;
+      while (time[crnt] == -1) {
+        time[crnt] = sum1 - sum2;
+        sum2 += informTime[crnt];
+        crnt = manager[crnt];
+      }
+    }
+
+    return res + informTime[headID];
+  }
+};
diff --git a/README.md b/README.md
@@ -442,6 +442,7 @@ for solving problems.
 |  1367  |   Medium   | [Linked List in Binary Tree ](Problems/1367.cpp)                                                 |
 |  1372  |   Medium   | [Longest ZigZag Path in a Binary Tree](Problems/1372.cpp)                                        |
 |  1373  |    Hard    | [Maximum Sum BST in Binary Tree](Problems/1373.cpp)                                              |
+|  1376  |   Medium   | [Time Needed to Inform All Employees](Problems/1376.cpp)                                         |
 |  1379  |    Easy    | [Find a Corresponding Node of a Binary Tree in a Clone of That Tree](Problems/1379.cpp)          |
 |  1382  |   Medium   | [Balance a Binary Search Tree](Problems/1382.cpp)                                                |
 |  1396  |   Medium   | [Design Underground System](Problems/1396.cpp)                                                   |