#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const int N = 1010;
int n, *conf;
bool act[N];
vector<int> G[N];
int solve(int u)
{
if (u == n)
return 0;
bool can = true;
for (auto v : G[u]) if (act[v])
can = false;
int ans = 0;
if (can) {
act[u] = true;
ans = max(ans, conf[u]+solve(u+1));
}
act[u] = false;
ans = max(ans, solve(u+1));
return ans;
}
int dp[N][2];
void dfs(int u, int p)
{
dp[u][1] = conf[u];
for (auto v : G[u]) if (v != p) {
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int findSample(int n, int confidence[], int host[], int protocol[])
{
if (n > 100000) return -1;
::n = n;
conf = confidence;
for (int i = 1; i < n; ++i) {
if (protocol[i] != 0) {
for (auto v : G[host[i]]) {
G[i].push_back(v);
G[v].push_back(i);
}
}
if (protocol[i] != 1) {
G[i].push_back(host[i]);
G[host[i]].push_back(i);
}
}
if (n <= 10)
return solve(0);
if (protocol[1] == 1) {
int sum = 0;
for (int i = 0; i < n; ++i)
sum += conf[i];
return sum;
}
if (protocol[1] == 2) {
int mx = 0;
for (int i = 0; i < n; ++i)
mx = max(mx, conf[i]);
return mx;
}
dfs(0, 0);
return max(dp[0][0], dp[0][1]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
404 KB |
Output is correct |
4 |
Correct |
2 ms |
628 KB |
Output is correct |
5 |
Correct |
2 ms |
628 KB |
Output is correct |
6 |
Correct |
3 ms |
628 KB |
Output is correct |
7 |
Correct |
3 ms |
628 KB |
Output is correct |
8 |
Correct |
2 ms |
628 KB |
Output is correct |
9 |
Correct |
3 ms |
628 KB |
Output is correct |
10 |
Correct |
3 ms |
628 KB |
Output is correct |
11 |
Correct |
3 ms |
648 KB |
Output is correct |
12 |
Correct |
2 ms |
648 KB |
Output is correct |
13 |
Correct |
3 ms |
648 KB |
Output is correct |
14 |
Correct |
3 ms |
648 KB |
Output is correct |
15 |
Correct |
3 ms |
648 KB |
Output is correct |
16 |
Correct |
2 ms |
648 KB |
Output is correct |
17 |
Correct |
2 ms |
648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
648 KB |
Output is correct |
2 |
Correct |
2 ms |
648 KB |
Output is correct |
3 |
Correct |
3 ms |
724 KB |
Output is correct |
4 |
Correct |
4 ms |
724 KB |
Output is correct |
5 |
Correct |
2 ms |
724 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
2 ms |
724 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
3 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1516 KB |
Output is correct |
2 |
Correct |
17 ms |
4448 KB |
Output is correct |
3 |
Correct |
2 ms |
4448 KB |
Output is correct |
4 |
Correct |
10 ms |
4448 KB |
Output is correct |
5 |
Correct |
12 ms |
4508 KB |
Output is correct |
6 |
Correct |
2 ms |
4508 KB |
Output is correct |
7 |
Correct |
4 ms |
4508 KB |
Output is correct |
8 |
Correct |
4 ms |
4508 KB |
Output is correct |
9 |
Correct |
2 ms |
4508 KB |
Output is correct |
10 |
Correct |
13 ms |
4832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4832 KB |
Output is correct |
2 |
Correct |
2 ms |
4832 KB |
Output is correct |
3 |
Correct |
3 ms |
4832 KB |
Output is correct |
4 |
Correct |
2 ms |
4832 KB |
Output is correct |
5 |
Correct |
3 ms |
4832 KB |
Output is correct |
6 |
Correct |
2 ms |
4832 KB |
Output is correct |
7 |
Correct |
2 ms |
4832 KB |
Output is correct |
8 |
Correct |
3 ms |
4832 KB |
Output is correct |
9 |
Correct |
2 ms |
4832 KB |
Output is correct |
10 |
Correct |
3 ms |
4832 KB |
Output is correct |
11 |
Correct |
3 ms |
4832 KB |
Output is correct |
12 |
Correct |
3 ms |
4832 KB |
Output is correct |
13 |
Correct |
2 ms |
4832 KB |
Output is correct |
14 |
Correct |
3 ms |
4832 KB |
Output is correct |
15 |
Correct |
3 ms |
4832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4832 KB |
Output is correct |
2 |
Correct |
2 ms |
4832 KB |
Output is correct |
3 |
Correct |
2 ms |
4832 KB |
Output is correct |
4 |
Correct |
2 ms |
4832 KB |
Output is correct |
5 |
Correct |
3 ms |
4832 KB |
Output is correct |
6 |
Correct |
2 ms |
4832 KB |
Output is correct |
7 |
Correct |
2 ms |
4832 KB |
Output is correct |
8 |
Correct |
3 ms |
4832 KB |
Output is correct |
9 |
Correct |
2 ms |
4832 KB |
Output is correct |
10 |
Correct |
3 ms |
4832 KB |
Output is correct |
11 |
Incorrect |
3 ms |
4832 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4832 KB |
Output is correct |
2 |
Correct |
2 ms |
4832 KB |
Output is correct |
3 |
Correct |
2 ms |
4832 KB |
Output is correct |
4 |
Correct |
2 ms |
4832 KB |
Output is correct |
5 |
Correct |
3 ms |
4832 KB |
Output is correct |
6 |
Correct |
3 ms |
4832 KB |
Output is correct |
7 |
Correct |
2 ms |
4832 KB |
Output is correct |
8 |
Correct |
2 ms |
4832 KB |
Output is correct |
9 |
Correct |
3 ms |
4832 KB |
Output is correct |
10 |
Correct |
2 ms |
4832 KB |
Output is correct |
11 |
Correct |
2 ms |
4832 KB |
Output is correct |
12 |
Runtime error |
44 ms |
4832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |