#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
/*
SUBTASK 4
vector<int> take, not_take;
vector<vector<int>> children;
void dfs(int u, int confidence[]){
take[u] += confidence[u];
for (int v : children[u]){
dfs(v, confidence);
take[u] += not_take[v];
not_take[u] += max(not_take[v], take[v]);
}
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
children.resize(n);
for (int i=1; i<n; i++){
children[host[i]].push_back(i);
}
take = not_take = vector<int>(n);
dfs(0, confidence);
return max(take[0], not_take[0]);
}*/
/*
SUBTASK 2
int findSample(int n,int confidence[],int host[],int protocol[]){
int ans = 0;
for (int i=0; i<n; i++) ans += confidence[i];
return ans;
}
*/
/*
int findSample(int n,int confidence[],int host[],int protocol[]){
int ans = 0;
for (int i=0; i<n; i++) ans = max(confidence[i], ans);
return ans;
}*/
int findSample(int n,int confidence[],int host[],int protocol[]){
int ans = 0;
vector<vector<int>> graph(n);
for (int i=1; i<n; i++){
if (protocol[i] == 0 || protocol[i] == 2){
graph[host[i]].push_back(i);
graph[i].push_back(host[i]);
}
if (protocol[i] == 1 || protocol[i] == 2){
for (int v : graph[host[i]]){
if (v != i){
graph[v].push_back(i);
graph[i].push_back(v);
}
}
}
}
/*for (int i=0; i<n; i++){
cout << i << ": ";
for (int x : graph[i]) cout << x << " ";
cout << endl;
}
for (int i=0; i<n; i++) cout << confidence[i] << " ";
cout << endl;
*/
int res = 0;
for (int i=0; i< (1 << n); i++){
//cout << "i: " << i << endl;
bool possible = true;
int val = 0;
for (int u=0; u<n && possible; u++){
if ((i & (1 << u)) != 0){
for (int v : graph[u]){
if ((i & (1 << v)) != 0){
//cout << i << " " << u << " " << v << endl;
possible = false;
break;
}
}
//cout << "test " << endl;
val += confidence[u];
}
}
if (possible) {
//cout << i << ": " << val << endl;
res = max(res, val);
}
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |