for each new edge [a,b] improve all [b..n] nodes lengths and siblings of each
Approach
pay attention to suspicous words
Complexity
Time complexity: $$O(qn)$$
Space complexity: $$O(q + n)$$
Code
fun shortestDistanceAfterQueries(n: Int, queries: Array<IntArray>): IntArray {
val g = Array(n) { mutableListOf(min(n - 1, it + 1)) }
val len = IntArray(n) { it }; val q = ArrayDeque<Pair<Int, Int>>()
return queries.map { (a, b) ->
g[a] += b; q += b to len[a] + 1
while (q.size > 0) {
val (x, s) = q.removeFirst()
if (len[x] <= s) continue
len[x] = s
for (sibl in g[x]) q += sibl to s + 1
}
len[n - 1]
}.toIntArray()
}
pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let (mut len, mut q) = ((0..n).collect::<Vec<_>>(), vec![]);
let mut g: Vec<_> = (0..n).map(|i| vec![(n - 1).min(i + 1)]).collect();
queries.iter().map(|e| {
let a = e[0] as usize; let b = e[1] as usize;
g[a].push(b); q.push((b, 1 + len[a]));
while let Some((x, s)) = q.pop() {
if len[x] <= s { continue }
len[x] = s;
q.extend(g[x].iter().map(|sibl| (*sibl, 1 + s)))
}; len[n - 1] as i32
}).collect()
}
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
vector<int> d(n); for (int i = n; i--;) d[i] = i;
vector<int> r; vector<vector<int>> g(n);
for (auto e: queries) {
int a = e[0], b = e[1];
g[b].push_back(a);
for (int x = b; x < n; ++x) {
d[x] = min(d[x], d[x - 1] + 1);
for (int sibl: g[x]) d[x] = min(d[x], d[sibl] + 1);
}
r.push_back(d[n - 1]);
} return r;
}
