leetcode

commit 807ebd3ef2467af2663643631acbf9cb7c825a9d
parent 285ad319ff62d64c3a600b92b6e8fda8ff569ba1
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 24 Dec 2024 12:37:20 +0100

Daily Problem

Diffstat:
A
Problems/3203.cpp
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 49 insertions(+), 0 deletions(-)
diff --git a/Problems/3203.cpp b/Problems/3203.cpp
@@ -0,0 +1,48 @@
+class Solution {
+    using vvi = vector<vector<int>>;
+
+    static int middle(const vvi &edges) {
+        static int count[100001];
+        const int n = size(edges) + 1;
+        vvi adj(n);
+
+        memset(count, 0x00, sizeof(count));
+
+        for (const auto &edge : edges) {
+            adj[edge[0]].push_back(edge[1]);
+            adj[edge[1]].push_back(edge[0]);
+            count[edge[0]]++;
+            count[edge[1]]++;
+        }
+
+        queue<int> q;
+        for (int i = 0; i < n; i++) {
+            if (count[i] != 1) continue;
+            q.push(i);
+        }
+
+        int crnt = 0, left = n, lvl;
+        for (lvl = 0; left > 2; lvl++) {
+            left -= size(q);
+
+            for (int k = size(q); k > 0; k--) {
+                crnt = q.front(), q.pop();
+
+                for (const auto next : adj[crnt]) {
+                    if (--count[next] != 1) continue;
+                    q.push(next);
+                }
+            }
+        }
+
+        return 2 * lvl + (left == 2);
+    }
+
+  public:
+    int minimumDiameterAfterMerge(const vvi &edges1, const vvi &edges2) const {
+        const auto d1 = middle(edges1);
+        const auto d2 = middle(edges2);
+
+        return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1});
+    }
+};
diff --git a/README.md b/README.md
@@ -1483,6 +1483,7 @@ reference and a base for solving problems.
 |  3191  |   Medium   | [Minimum Operations to Make Binary Array Elements Equal to One I](Problems/3191.cpp)               |
 |  3192  |   Medium   | [Minimum Operations to Make Binary Array Elements Equal to One II](Problems/3192.cpp)              |
 |  3195  |   Medium   | [Find the Minimum Area to Cover All Ones I](Problems/3195.cpp)                                     |
+|  3203  |    Hard    | [Find Minimum Diameter After Merging Two Trees](Problems/3203.cpp)                                 |
 |  3211  |   Medium   | [Generate Binary Strings Without Adjacent Zeros](Problems/3211.cpp)                                |
 |  3212  |   Medium   | [Count Submatrices With Equal Frequency of X and Y](Problems/3212.cpp)                             |
 |  3217  |   Medium   | [Delete Nodes From Linked List Present in Array](Problems/3217.cpp)                                |