leetcode

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

3067.cpp (1303B)

      1 class Solution {
      2   public:
      3     vector<int> countPairsOfConnectableServers(const vector<vector<int>> &edges,
      4                                                const int signalSpeed) const {
      5         const int n = size(edges) + 1;
      6         vector<vector<pair<int, int>>> adj(n);
      7 
      8         for (const auto &edge : edges) {
      9             adj[edge[0]].emplace_back(edge[1], edge[2]);
     10             adj[edge[1]].emplace_back(edge[0], edge[2]);
     11         }
     12 
     13         static int cnt[1001], res[1001];
     14         stack<tuple<int, int, int>> st;
     15 
     16         memset(res, 0x00, n * sizeof(*res));
     17         for (int i = 0; i < n; i++) {
     18             memset(cnt, 0x00, sizeof(cnt));
     19             for (int j = 0; j < size(adj[i]); j++) {
     20                 st.emplace(i, adj[i][j].first, adj[i][j].second);
     21 
     22                 while (!st.empty()) {
     23                     const auto [p, c, t] = st.top();
     24                     st.pop();
     25                     if (t % signalSpeed == 0) cnt[j]++;
     26                     for (const auto [n, w] : adj[c]) {
     27                         if (n == p) continue;
     28                         st.emplace(c, n, t + w);
     29                     }
     30                 }
     31 
     32                 for (int k = 0; k < j; k++)
     33                     res[i] += cnt[j] * cnt[k];
     34             }
     35         }
     36 
     37         return vector<int>(res, res + n);
     38     }
     39 };