#include "friend.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <cassert>
using namespace std;
int adj[15][15], seen[1005], dp[1005][2], conf[1005];
vector<int> graph[1005];
void dfs(int x, int p) {
dp[x][0] = conf[x];
for (int v : graph[x]) if (v != p) {
dfs(v, x);
dp[x][1] += dp[v][0];
dp[x][0] += dp[v][1];
}
dp[x][0] = max(dp[x][0], dp[x][1]);
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
int st2 = 1, st3 = 1, st4 = 1;
for (int i = 0; i < n; i++) conf[i] = confidence[i];
for (int i = 1; i < n; i++) {
if (protocol[i] == 0) st2 = st3 = 0;
else if (protocol[i] == 2) st3 = st4 = 0;
else st2 = st4 = 0;
}
if (st2) {
int ans = 0;
for (int i = 0; i < n; i++) ans += confidence[i];
return ans;
} else if (st3) {
int ans = 0;
for (int i = 0; i < n; i++) ans = max(ans, confidence[i]);
return ans;
} else if (st4) {
for (int i = 1; i < n; i++) {
graph[host[i]].push_back(i);
graph[i].push_back(host[i]);
}
dfs(0, 0);
return dp[0][0];
} else if (n <= 10) {
int ans = 0;
for (int i = 1; i < n; i++) {
if (protocol[i] == 0) {
adj[i][host[i]] = adj[host[i]][i] = 1;
} else if (protocol[i] == 1) {
for (int v = 0; v < n; v++) if (adj[host[i]][v])
adj[i][v] = adj[v][i] = 1;
} else {
adj[i][host[i]] = adj[host[i]][i] = 1;
for (int v = 0; v < n; v++) if (adj[host[i]][v])
adj[i][v] = adj[v][i] = 1;
}
}
for (int s = 0; s < (1 << n); s++) {
int cooked = 0;
for (int a = 0; a < n; a++) for (int b = a+1; b < n; b++) {
if (((s >> a) & (s >> b) & 1) && adj[a][b]) cooked = 1;
}
if (!cooked) {
int res = 0;
for (int i = 0; i < n; i++) if ((s >> i) & 1) res += conf[i];
ans = max(ans, res);
}
}
return ans;
} else assert(false);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
360 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
6 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
432 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
424 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
6 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Runtime error |
37 ms |
2936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |