leetcode

Solution to some Leetcode problems written in C++

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

2246.cpp (1030B)

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