leetcode

commit db651b59c2b61fbd55c10b73ec0722631247b3ed
parent e9693c551689f7326d12adebcc0239d537f3aa40
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 16 Apr 2024 19:07:05 +0200

1 Random Problem

Diffstat:
A
Problems/3067.cpp
 | 
39
+++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 40 insertions(+), 0 deletions(-)
diff --git a/Problems/3067.cpp b/Problems/3067.cpp
@@ -0,0 +1,39 @@
+class Solution {
+  public:
+    vector<int> countPairsOfConnectableServers(const vector<vector<int>> &edges,
+                                               const int signalSpeed) const {
+        const int n = size(edges) + 1;
+        vector<vector<pair<int, int>>> adj(n);
+
+        for (const auto &edge : edges) {
+            adj[edge[0]].emplace_back(edge[1], edge[2]);
+            adj[edge[1]].emplace_back(edge[0], edge[2]);
+        }
+
+        static int cnt[1001], res[1001];
+        stack<tuple<int, int, int>> st;
+
+        memset(res, 0x00, n * sizeof(*res));
+        for (int i = 0; i < n; i++) {
+            memset(cnt, 0x00, sizeof(cnt));
+            for (int j = 0; j < size(adj[i]); j++) {
+                st.emplace(i, adj[i][j].first, adj[i][j].second);
+
+                while (!st.empty()) {
+                    const auto [p, c, t] = st.top();
+                    st.pop();
+                    if (t % signalSpeed == 0) cnt[j]++;
+                    for (const auto [n, w] : adj[c]) {
+                        if (n == p) continue;
+                        st.emplace(c, n, t + w);
+                    }
+                }
+
+                for (int k = 0; k < j; k++)
+                    res[i] += cnt[j] * cnt[k];
+            }
+        }
+
+        return vector<int>(res, res + n);
+    }
+};
diff --git a/README.md b/README.md
@@ -1193,6 +1193,7 @@ for solving problems.
 |  3016  |   Medium   | [Minimum Number of Pushes to Type Word II](Problems/3016.cpp)                                      |
 |  3034  |   Medium   | [Number of Subarrays That Match a Pattern I](Problems/3034.cpp)                                    |
 |  3039  |   Medium   | [Apply Operations to Make String Empty](Problems/3039.cpp)                                         |
+|  3067  |   Medium   | [Count Pairs of Connectable Servers in a Weighted Tree Network](Problems/3067.cpp)                 |
 |  3070  |   Medium   | [Count Submatrices with Top-Left Element and Sum Less Than k](Problems/3070.cpp)                   |
 |  3100  |   Medium   | [Water Bottles II](Problems/3100.cpp)                                                              |
 |  3101  |   Medium   | [Count Alternating Subarrays](Problems/3101.cpp)                                                   |