leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

3243.cpp (911B)

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 };