#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const int MAX_N = 1e5 + 5;
int N, C[MAX_N];
int dp[MAX_N][2];
vector <int> graph[MAX_N];
bool visited[15][15];
void dfs(int u) {
dp[u][1] = C[u];
for(auto v : graph[u]) {
dfs(v);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[]){
N = n;
int cnt[3] = {};
for(int i = 0; i < N; i++) {
C[i] = confidence[i];
}
for(int i = 1; i < N; i++) {
cnt[protocol[i]]++;
}
int ans = 0;
if(N <= 10) {
for(int i = 1; i < N; i++) {
if(protocol[i] == 0) {
visited[i][host[i]] = visited[host[i]][i] = true;
}
else if(protocol[i] == 1) {
for(int j = 0; j < N; j++) {
if(visited[j][host[i]] == true) {
visited[i][j] = visited[j][i] = true;
}
}
}
else if(protocol[i] == 2) {
for(int j = 0; j < N; j++) {
if(visited[j][host[i]] == true) {
visited[i][j] = visited[j][i] = true;
}
}
visited[i][host[i]] = visited[host[i]][i] = true;
}
}
for(int mask = 0; mask < (1<<N); mask++) {
int sum = 0;
bool ok = true;
for(int i = 0; i < N; i++) {
if(mask & (1<<i)) {
sum += C[i];
for(int j = 0; j < N; j++) {
if((mask & (1<<j)) and visited[i][j] == true) {
ok = false;
}
}
}
}
if(ok == true) {
ans = max(ans, sum);
}
}
}
else if(cnt[0] == N - 1) {
for(int i = 1; i < N; i++) {
graph[host[i]].push_back(i);
}
dfs(0);
ans = max(dp[0][0], dp[0][1]);
}
else if(cnt[1] == N - 1) {
for(int i = 0; i < N; i++) {
ans += confidence[i];
}
}
else if(cnt[2] == N - 1) {
for(int i = 0; i < N; i++) {
ans = max(ans, confidence[i]);
}
}
else {
// do something
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2656 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 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 |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 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 |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 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 |
3 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2560 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 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 |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
3 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 |
2 ms |
2584 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2664 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2772 KB |
Output is correct |
14 |
Correct |
2 ms |
2656 KB |
Output is correct |
15 |
Correct |
2 ms |
2668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 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 |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 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 |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Incorrect |
28 ms |
4184 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |