#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int N = 2005;
vector<int> v;
vector<int> edge[N];
int val[N];
bool visited[N];
int orson[N];
int oroogui[N];
bool b[20][20];
void dfs(int k) {
visited[k] = 1;
for(auto x: edge[k]) {
if(visited[x] == 1) continue;
dfs(x);
orson[k] += oroogui[x];
oroogui[k] += max(orson[x], oroogui[x]);
}
orson[k] += val[k];
}
int tmp_n;
int ans = 0;
void go(string s) {
if(s.size() == tmp_n + 1) {
int tur = 0;
for(int i = 0; i < s.size(); i ++) {
for(int j = i + 1; j < s.size(); j ++) {
if(b[i][j] == 1 && s[i] == '1' && s[j] == '1') return;
}
if(s[i] == '1') tur += val[i];
}
ans = max(ans, tur);
return;
}
string tmp = s + "0";
go(tmp);
tmp = s + "1";
go(tmp);
}
// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[]){
tmp_n = n;
for(int i = 0; i < n; i++) val[i] = confidence[i];
if(n <= 10) {
// subtask 1
for(int i = 1; i < n; i ++) {
if(protocol[i] == 0) {
b[i][host[i]] = 1;
b[host[i]][i] = 1;
edge[i].pb(host[i]);
edge[host[i]].pb(i);
}
else {
for(auto x: edge[host[i]]) {
b[x][i] = 1;
b[i][x] = 1;
edge[x].pb(i);
edge[i].pb(x);
}
if(protocol[i] == 2) {
b[host[i]][i] = 1;
b[i][host[i]] = 1;
edge[i].pb(host[i]);
edge[host[i]].pb(i);
}
}
}
go("");
return ans;
}
int x=0, y =0 , z = 0;
for(int i = 1; i < n; i ++) {
if(protocol[i] == 0) x ++;
if(protocol[i] == 1) y ++;
if(protocol[i] == 2) z ++;
}
for(int i = 1; i < n; i ++) {
// host[i] / protocol[i]
edge[i].pb(host[i]);
edge[host[i]].pb(i);
}
int sum = 0;
for(int i = 0; i < n; i ++) sum += confidence[i];
int mx = 0;
for(int i = 0; i < n; i ++) mx = max(mx, confidence[i]);
if(y == n - 1) return sum;
if(z == n - 1) return mx;
for(int i = 0; i < n; i++) val[i] = confidence[i];
dfs(0);
return max(orson[0], oroogui[0]);
}
Compilation message
friend.cpp: In function 'void go(std::string)':
friend.cpp:36:14: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | if(s.size() == tmp_n + 1) {
| ~~~~~~~~~^~~~~~~~~~~~
friend.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i < s.size(); i ++) {
| ~~^~~~~~~~~~
friend.cpp:39:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int j = i + 1; j < s.size(); j ++) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
356 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
356 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
392 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
488 KB |
Output is correct |
10 |
Correct |
1 ms |
372 KB |
Output is correct |
11 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Runtime error |
25 ms |
4048 KB |
Execution killed with signal 11 |
13 |
Halted |
0 ms |
0 KB |
- |