#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000;
bool matr[MAX_N][MAX_N];
vector<int> graph[MAX_N];
void buildGraph(int n, int *host, int *protocol) {
for(int i = 1; i < n; ++i) {
if(protocol[i] == 0)
matr[i][host[i]] = matr[host[i]][i] = true;
else if(protocol[i] == 1) {
for(int j = 0; j < n; ++j)
if(matr[host[i]][j])
matr[i][j] = matr[j][i] = true;
} else {
matr[i][host[i]] = matr[host[i]][i] = true;
for(int j = 0; j < n; ++j)
if(matr[host[i]][j])
matr[i][j] = matr[j][i] = true;
}
}
for(int i = 0; i < n; ++i)
matr[i][i] = false;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(matr[i][j])
graph[i].push_back(j);
}
int subtask2(int n, int *confidence, int *host, int *protocol) {
int sum = 0;
for(int i = 0; i < n; ++i)
sum += confidence[i];
return sum;
}
int subtask3(int n, int *confidence, int *host, int *protocol) {
int rez = 0;
for(int i = 0; i < n; ++i)
rez = max(rez, confidence[i]);
return rez;
}
int subtask4(int n, int *confidence, int *host, int *protocol) {
return 0;
}
int subtask5(int n, int *confidence, int *host, int *protocol) {
return 0;
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
int rez = 0;
if(n <= 10) {
buildGraph(n, host, protocol);
for(int mask = 0; mask < (1 << n); ++mask) {
int sum = 0;
bool ok = true;
for(int i = 0; i < n; ++i) {
if((1 << i) & mask)
sum = sum + confidence[i];
for(int j = 0; j < n; ++j)
if(((1 << i) & mask) != 0 && ((1 << j) & mask) != 0 && matr[i][j])
ok = false;
}
if(ok)
rez = max(rez, sum);
}
} else {
int nr[3];
nr[0] = nr[1] = nr[2] = 0;
for(int i = 1; i < n; ++i)
nr[protocol[i]]++;
if(nr[0] == 0 && nr[1] == n - 1 && nr[2] == 0)
rez = subtask2(n, confidence, host, protocol);
else if(nr[0] == 0 && nr[1] == 0 && nr[2] == n - 1)
rez = subtask3(n, confidence, host, protocol);
else if(nr[0] == n - 1 && nr[1] == 0 && nr[2] == 0)
rez = subtask4(n, confidence, host, protocol);
else if(nr[2] == 0)
rez = subtask5(n, confidence, host, protocol);
}
return rez;
}
