leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

3243.cpp (911B)

      1 class Solution {
      2   public:
      3     vector<int> shortestDistanceAfterQueries(int n, const vector<vector<int>> &queries) const {
      4         vector<vector<int>> adj(n);
      5         static int len[501];
      6 
      7         len[n - 1] = 0;
      8         for (int i = 1; i < n; i++) {
      9             adj[i].push_back(i - 1);
     10             len[i - 1] = n - i;
     11         }
     12 
     13         vector<int> res;
     14         queue<pair<int, int>> q;
     15         for (const auto query : queries) {
     16             for (q.emplace(query[0], len[query[1]]); !q.empty();) {
     17                 const auto [crnt, parent] = q.front();
     18                 q.pop();
     19 
     20                 if (len[crnt] <= parent + 1) continue;
     21 
     22                 len[crnt] = parent + 1;
     23                 for (const int next : adj[crnt])
     24                     q.emplace(next, len[crnt]);
     25             }
     26 
     27             adj[query[1]].push_back(query[0]);
     28             res.push_back(len[0]);
     29         }
     30 
     31         return res;
     32     }
     33 };