leetcode

commit 3fa12cfdd2b561baa15de38dfaed99e72d982c19
parent f75969e6c9cc596157aa5aca205ee7795a4a4c31
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 29 Apr 2023 15:11:54 +0200

Daily Problem

Diffstat:
A
Problems/1697.cpp
 | 
50
++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 51 insertions(+), 0 deletions(-)
diff --git a/Problems/1697.cpp b/Problems/1697.cpp
@@ -0,0 +1,50 @@
+class UnionFind {
+  int n, cnt = n;
+  vector<int> root, size;
+
+public:
+  UnionFind(int n) : n(n), root(n), size(n, 1) {
+    iota(root.begin(), root.end(), 0);
+  }
+
+  int find(int x) {
+    while (x != root[x]) x = root[x] = root[root[x]];
+    return x;
+  }
+
+  void join(int x, int y) {
+    x = find(x), y = find(y);
+    if (x != y) {
+      if (size[x] > size[y]) swap(x, y);
+      root[x] = y;
+      size[y] += size[x];
+      cnt--;
+    }
+  }
+
+  int count() { return cnt; }
+  bool connected(int x, int y) { return find(x) == find(y); }
+};
+
+class Solution {
+public:
+  vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>> &edges,
+                                         vector<vector<int>> &queries) {
+    vector<bool> res(queries.size());
+    UnionFind uf(n);
+
+    for (int i = 0; i < queries.size(); ++i) queries[i].push_back(i);
+
+    const auto cmp = [](auto &a, auto &b) { return a[2] < b[2]; };
+    sort(begin(queries), end(queries), cmp);
+    sort(begin(edges), end(edges), cmp);
+
+    int i = 0;
+    for (auto &q : queries) {
+      for (; i < edges.size() && edges[i][2] < q[2]; i++)
+        uf.join(edges[i][0], edges[i][1]);
+      res[q[3]] = uf.connected(q[0], q[1]);
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -465,6 +465,7 @@ for solving problems.
 |  1672  |    Easy    | [Richest Customer Wealth](Problems/1672.cpp)                                                     |
 |  1675  |    Hard    | [Minimize Deviation in Array](Problems/1675.cpp)                                                 |
 |  1696  |   Medium   | [Jump Game VI](Problems/1696.cpp)                                                                |
+|  1697  |    Hard    | [Checking Existence of Edge Length Limited Paths](Problems/1697.cpp)                             |
 |  1700  |    Easy    | [Number of Students Unable to Eat Lunch](Problems/1700.cpp)                                      |
 |  1704  |    Easy    | [Determine if String Halves Are Alike](Problems/1704.cpp)                                        |
 |  1706  |   Medium   | [Where Will the Ball Fall](Problems/1706.cpp)                                                    |