#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
#include "friend.h"
using namespace std;
using llong = long long;
const int maxN = 100'005;
set<int> nei[maxN];
enum Protocol { ME = 0, MY = 1, WE = 2 };
pair<int, int> SolveTree(int v, int* a)
{
pair<int, int> res(a[v], 0);
for (int to: nei[v])
{
pair<int, int> cur = SolveTree(to, a);
res.first += cur.second;
res.second += max(cur.first, cur.second);
}
return res;
}
int findSample(int n, int a[], int host[], int prot[]) {
if (count(prot + 1, prot + n, ME) == n - 1) {
for (int i = 1; i < n; ++i)
nei[host[i]].insert(i);
auto p = SolveTree(0, a);
return max(p.first, p.second);
}
if (count(prot + 1, prot + n, MY) == n - 1)
return accumulate(a, a + n, 0);
if (count(prot + 1, prot + n, WE) == n - 1)
return *max_element(a, a + n);
if (n <= 10)
{
bool g[10][10];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
g[i][j] = false;
for (int i = 1; i < n; ++i)
{
int j = host[i];
if (prot[i] == ME)
g[i][j] = g[j][i] = true;
else
{
for (int k = 0; k < n; ++k)
if (g[j][k])
g[i][k] = g[k][i] = true;
if (prot[i] == WE)
g[i][j] = g[j][i] = true;
}
}
int ans = 0;
for (int mask = 1; mask < (1 << n); ++mask)
{
bool ok = true;
int cur = 0;
for (int i = 0; i < n; ++i)
{
if (!(mask & (1 << i))) continue;
cur += a[i];
for (int j = i + 1; j < n; ++j) {
if (!(mask & (1 << j))) continue;
if (g[i][j])
ok = false;
}
}
if (ok) ans = max(ans, cur);
}
return ans;
}
int ans = 0;
for (int i = n - 1; i > 0; --i)
{
if (prot[i] == ME) {
ans += a[i];
a[host[i]] = max(a[host[i]] - a[i], 0);
}
else if (prot[i] == MY)
a[host[i]] += a[i];
else
a[host[i]] = max(a[host[i]], a[i]);
}
return ans + a[0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
4 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
4992 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
3 ms |
4992 KB |
Output is correct |
8 |
Correct |
3 ms |
4992 KB |
Output is correct |
9 |
Correct |
4 ms |
5120 KB |
Output is correct |
10 |
Correct |
3 ms |
4992 KB |
Output is correct |
11 |
Correct |
3 ms |
4992 KB |
Output is correct |
12 |
Correct |
4 ms |
4992 KB |
Output is correct |
13 |
Correct |
4 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
4992 KB |
Output is correct |
15 |
Correct |
3 ms |
5120 KB |
Output is correct |
16 |
Correct |
4 ms |
4992 KB |
Output is correct |
17 |
Correct |
4 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
4992 KB |
Output is correct |
6 |
Correct |
4 ms |
4992 KB |
Output is correct |
7 |
Correct |
4 ms |
4992 KB |
Output is correct |
8 |
Correct |
4 ms |
5120 KB |
Output is correct |
9 |
Correct |
4 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
4 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
4992 KB |
Output is correct |
6 |
Correct |
4 ms |
4992 KB |
Output is correct |
7 |
Correct |
4 ms |
4992 KB |
Output is correct |
8 |
Correct |
4 ms |
4992 KB |
Output is correct |
9 |
Correct |
4 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
4 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
4992 KB |
Output is correct |
8 |
Correct |
4 ms |
5120 KB |
Output is correct |
9 |
Correct |
4 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
11 |
Correct |
4 ms |
4992 KB |
Output is correct |
12 |
Correct |
4 ms |
5120 KB |
Output is correct |
13 |
Correct |
4 ms |
5120 KB |
Output is correct |
14 |
Correct |
3 ms |
4992 KB |
Output is correct |
15 |
Correct |
4 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
4 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
4992 KB |
Output is correct |
6 |
Correct |
4 ms |
4992 KB |
Output is correct |
7 |
Correct |
4 ms |
4992 KB |
Output is correct |
8 |
Correct |
3 ms |
5120 KB |
Output is correct |
9 |
Correct |
4 ms |
5120 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
11 |
Correct |
4 ms |
4992 KB |
Output is correct |
12 |
Correct |
4 ms |
4992 KB |
Output is correct |
13 |
Correct |
4 ms |
4992 KB |
Output is correct |
14 |
Correct |
4 ms |
4992 KB |
Output is correct |
15 |
Correct |
4 ms |
4992 KB |
Output is correct |
16 |
Correct |
4 ms |
5120 KB |
Output is correct |
17 |
Correct |
4 ms |
4992 KB |
Output is correct |
18 |
Correct |
4 ms |
4992 KB |
Output is correct |
19 |
Correct |
4 ms |
4992 KB |
Output is correct |
20 |
Correct |
4 ms |
4992 KB |
Output is correct |
21 |
Correct |
4 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
4992 KB |
Output is correct |
6 |
Correct |
4 ms |
4992 KB |
Output is correct |
7 |
Correct |
4 ms |
4992 KB |
Output is correct |
8 |
Correct |
4 ms |
4992 KB |
Output is correct |
9 |
Correct |
4 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
11 |
Correct |
4 ms |
4992 KB |
Output is correct |
12 |
Correct |
38 ms |
7416 KB |
Output is correct |
13 |
Correct |
22 ms |
6272 KB |
Output is correct |
14 |
Correct |
35 ms |
7160 KB |
Output is correct |
15 |
Correct |
34 ms |
7160 KB |
Output is correct |