-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
maximum-score-of-a-node-sequence.cpp
38 lines (37 loc) · 1.24 KB
/
maximum-score-of-a-node-sequence.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Time: O(|V| + |E|)
// Space: O(|V|)
// graph
class Solution {
public:
int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
using PII = pair<int, int>;
using Heap = vector<PII>;
const auto& find_top3 = [&scores](const auto& x, Heap *top3) {
top3->emplace_back(scores[x], x); push_heap(begin(*top3), end(*top3), greater<PII>());
if (size(*top3) > 3) {
pop_heap(begin(*top3), end(*top3), greater<PII>()); top3->pop_back();
}
};
vector<Heap> top3(size(scores));
for (const auto& e : edges) {
find_top3(e[1], &top3[e[0]]);
find_top3(e[0], &top3[e[1]]);
}
int result = -1;
for (const auto& e : edges) {
const int a = e[0], b = e[1];
for (const auto& [_, c] : top3[a]) {
if (c == b) {
continue;
}
for (const auto& [_, d] : top3[b]) {
if (d == a || d == c) {
continue;
}
result = max(result, scores[a] + scores[b] + scores[c] + scores[d]);
}
}
}
return result;
}
};