leetcode

commit 2847b1ee0ab72094a43ca4a1803d2d24676f28d7
parent 83a17d55c1e80259271736114f75b0f81daa8475
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 27 Nov 2024 16:10:30 +0100

Daily Problem

Diffstat:
A
Problems/3243.cpp
 | 
33
+++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/3243.cpp b/Problems/3243.cpp
@@ -0,0 +1,33 @@
+class Solution {
+  public:
+    vector<int> shortestDistanceAfterQueries(int n, const vector<vector<int>> &queries) const {
+        vector<vector<int>> adj(n);
+        static int len[501];
+
+        len[n - 1] = 0;
+        for (int i = 1; i < n; i++) {
+            adj[i].push_back(i - 1);
+            len[i - 1] = n - i;
+        }
+
+        vector<int> res;
+        queue<pair<int, int>> q;
+        for (const auto query : queries) {
+            for (q.emplace(query[0], len[query[1]]); !q.empty();) {
+                const auto [crnt, parent] = q.front();
+                q.pop();
+
+                if (len[crnt] <= parent + 1) continue;
+
+                len[crnt] = parent + 1;
+                for (const int next : adj[crnt])
+                    q.emplace(next, len[crnt]);
+            }
+
+            adj[query[1]].push_back(query[0]);
+            res.push_back(len[0]);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1465,6 +1465,7 @@ reference and a base for solving problems.
 |  3227  |   Medium   | [Vowels Game in a String](Problems/3227.cpp)                                                       |
 |  3228  |   Medium   | [Maximum Number of Operations to Move Ones to the End](Problems/3228.cpp)                          |
 |  3239  |   Medium   | [Minimum Number of Flips to Make Binary Grid Palindromic I](Problems/3239.cpp)                     |
+|  3243  |   Medium   | [Shortest Distance After Road Addition Queries I](Problems/3243.cpp)                               |
 |  3249  |   Medium   | [Count the Number of Good Nodes](Problems/3249.cpp)                                                |
 |  3254  |   Medium   | [Find the Power of K-Size Subarrays I](Problems/3254.cpp)                                          |
 |  3291  |   Medium   | [Minimum Number of Valid Strings to Form Target I](Problems/3291.cpp)                              |