leetcode

0 class Solution {

1 public:

2 vector<int> shortestDistanceAfterQueries(int n, const vector<vector<int>> &queries) const {

3 vector<vector<int>> adj(n);

4 static int len[501];

5

6 len[n - 1] = 0;

7 for (int i = 1; i < n; i++) {

8 adj[i].push_back(i - 1);

9 len[i - 1] = n - i;

10 }

11

12 vector<int> res;

13 queue<pair<int, int>> q;

14 for (const auto query : queries) {

15 for (q.emplace(query[0], len[query[1]]); !q.empty();) {

16 const auto [crnt, parent] = q.front();

17 q.pop();

18

19 if (len[crnt] <= parent + 1) continue;

20

21 len[crnt] = parent + 1;

22 for (const int next : adj[crnt])

23 q.emplace(next, len[crnt]);

24 }

25

26 adj[query[1]].push_back(query[0]);

27 res.push_back(len[0]);

28 }

29

30 return res;

31 }

32 };