#include <bits/stdc++.h>
using namespace std;
int n;
int co[100000];
int ho[100000];
int pro[100000];
int con[10][10];
vector<int> son[1000];
int dp[1000][2];
int ans(int now,int stat) {
if (dp[now][stat]!=-1) {
return dp[now][stat];
}
int ret=0;
if (stat==1) {
ret+=co[now];
}
if (stat==0) {
for(int i=0;i<son[now].size();i++) {
ret+=max(ans(son[now][i],0),ans(son[now][i],1));
}
}
else {
for(int i=0;i<son[now].size();i++) {
ret+=ans(son[now][i],0);
}
}
dp[now][stat]=ret;
return ret;
}
int findSample(int nn,int conf[],int hos[],int prot[]) {
n=nn;
for(int i=0;i<n;i++) {
co[i]=conf[i];
ho[i]=hos[i];
pro[i]=prot[i];
}
if (n<=10) {
for(int i=1;i<n;i++) {
if (pro[i]==0) {
con[ho[i]][i]=1;
con[i][ho[i]]=1;
}
if (pro[i]==1) {
for(int j=0;j<n;j++) {
if (con[ho[i]][j]==1) {
con[i][j]=1;
con[j][i]=1;
}
}
}
if (pro[i]==2) {
for(int j=0;j<n;j++) {
if (con[ho[i]][j]==1) {
con[i][j]=1;
con[j][i]=1;
}
}
con[ho[i]][i]=1;
con[i][ho[i]]=1;
}
}
int ret=0;
for(int i=0;i<(1<<n);i++) {
bool use[10];
memset(use,0,sizeof(use));
for(int j=0;j<n;j++) {
if ((i&(1<<j))!=0) {
use[j]=true;
}
}
bool flag=true;
for(int j=0;j<n;j++) {
for(int k=0;k<n;k++) {
if (con[k][j]==1&&use[k]&&use[j]) {
flag=false;
break;
}
}
}
if (!flag) {
continue;
}
int val=0;
for(int j=0;j<n;j++) {
if (use[j]) {
val+=co[j];
}
}
ret=max(ret,val);
}
return ret;
}
if (pro[1]==1) {
int ret=0;
for(int i=0;i<n;i++) {
ret+=co[i];
}
return ret;
}
for(int i=1;i<n;i++) {
son[ho[i]].push_back(i);
}
memset(dp,-1,sizeof(dp));
return max(ans(0,0),ans(0,1));
}
Compilation message
friend.cpp: In function 'int ans(int, int)':
friend.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<son[now].size();i++) {
~^~~~~~~~~~~~~~~~
friend.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<son[now].size();i++) {
~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 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 |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
384 KB |
Output is correct |
13 |
Correct |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
4 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 |
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 |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 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 |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 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 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 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 |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
384 KB |
Output is correct |
11 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 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 |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 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 |
4 ms |
384 KB |
Output is correct |
12 |
Runtime error |
46 ms |
5240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |