#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 20;
vector<pair<int, int>> ch[maxn];
int a[maxn];
int dp[maxn][2];
void dfs(int u) {
for (auto e: ch[u]) {
int v = e.first;
dfs(v);
}
int sum = a[u];
for (auto e: ch[u]) {
int v = e.first;
int op = e.second;
if (op == 1) {
sum += max(dp[v][0], dp[v][1]);
}
else {
sum += dp[v][0];
}
}
dp[u][1] = max(dp[u][1], sum);
int sz = ch[u].size();
vector<int> suf(sz);
sum = 0;
for (int i = sz - 1; i >= 0; i--) {
pair<int, int> e = ch[u][i];
int v = e.first;
int op = e.second;
if (op == 0) {
sum += max(dp[v][0], dp[v][1]);
}
else {
sum += dp[v][0];
}
suf[i] = sum;
}
sum = 0;
for (int i = 0; i < sz; i++) {
pair<int, int> e = ch[u][i];
int v = e.first;
int op = e.second;
if (op == 1) {
sum += dp[v][0];
dp[u][0] = max(dp[u][0], sum + (i < sz - 1 ? suf[i + 1] : 0));
}
else {
int pref = sum + (op == 0 ? max(dp[v][0], dp[v][1]) : dp[v][0]);
dp[u][0] = max(dp[u][0], pref + (i < sz - 1 ? suf[i + 1] : 0));
sum += dp[v][0];
}
}
dp[u][0] = max(dp[u][0], sum);
sum = 0;
for (int i = 0; i < sz; i++) {
pair<int, int> e = ch[u][i];
int v = e.first;
int op = e.second;
if (op == 1) {
sum += max(dp[v][0], dp[v][1]);
dp[u][1] = max(dp[u][1], sum + (i < sz - 1 ? suf[i + 1] : 0));
}
else {
int pref = sum + max(dp[v][0], dp[v][1]);
dp[u][1] = max(dp[u][1], pref + (i < sz - 1 ? suf[i + 1] : 0));
sum += dp[v][0];
}
}
dp[u][1] = max(dp[u][1], sum);
}
int findSample(int n, int confidence[], int host[], int protocol[]){
for (int i = 0; i < n; i++) {
a[i] = confidence[i];
}
for (int v = 1; v < n; v++) {
ch[host[v]].emplace_back(v, protocol[v]);
}
for (int i = 0; i < n; i++) {
sort(ch[i].begin(), ch[i].end());
}
dfs(0);
return max(dp[0][0], dp[0][1]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2644 KB |
Output is correct |
13 |
Correct |
1 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2772 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2696 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2772 KB |
Output is correct |
10 |
Correct |
2 ms |
2772 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2668 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2664 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2596 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2680 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
32 ms |
6760 KB |
Output is correct |
13 |
Correct |
17 ms |
5364 KB |
Output is correct |
14 |
Correct |
29 ms |
7476 KB |
Output is correct |
15 |
Correct |
36 ms |
7528 KB |
Output is correct |