leetcode

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

2246.cpp (1030B)

      1 class Solution {
      2   public:
      3     int longestPath(vector<int> &parent, string s) {
      4         int n = parent.size();
      5 
      6         vector<vector<int>> adj(n);
      7         vector<int> pc(n, 0), count(n);
      8         for (int i = 1; i < n; i++)
      9             pc[parent[i]]++;
     10 
     11         queue<int> q;
     12         for (int i = 0; i < n; i++)
     13             if (pc[i] == 0) q.push(i);
     14 
     15         int res = 0;
     16         while (true) {
     17             int crnt = q.front();
     18             q.pop();
     19 
     20             int mx1 = 0, mx2 = 0;
     21             for (int c : adj[crnt]) {
     22                 int a = s[crnt] != s[c] ? count[c] : 0;
     23                 if (a > mx1) {
     24                     mx2 = mx1;
     25                     mx1 = a;
     26                 } else if (a > mx2) {
     27                     mx2 = a;
     28                 }
     29             }
     30             res = max(res, mx1 + mx2 + 1);
     31             count[crnt] = mx1 + 1;
     32 
     33             if (crnt == 0) break;
     34             int p = parent[crnt];
     35             adj[p].push_back(crnt);
     36             if (!--pc[p]) q.push(p);
     37         }
     38 
     39         return res;
     40     }
     41 };