# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
227995 |
2020-04-29T13:16:06 Z |
urd05 |
Friend (IOI14_friend) |
C++14 |
|
45 ms |
5240 KB |
#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];
vector<int> adj[1000];
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 p[1000];
int find(int a) {
if (p[a]<0) {
return a;
}
p[a]=find(p[a]);
return p[a];
}
void merge(int a,int b) {
if (a>b) {
swap(a,b);
}
a=find(a);
b=find(b);
if (a==b) {
return;
}
p[a]+=p[b];
p[b]=a;
}
bool visited[1000];
void maketree(int v) {
visited[v]=true;
for(int i=0;i<adj[v].size();i++) {
int next=adj[v][i];
if (!visited[next]) {
son[v].push_back(next);
maketree(next);
}
}
}
int getans(int now,int stat) {
if (dp[now][stat]!=-1) {
return dp[now][stat];
}
int ret=0;
if (stat==1) {
ret-=p[now];
}
if (stat==0) {
for(int i=0;i<son[now].size();i++) {
ret+=max(getans(son[now][i],0),getans(son[now][i],1));
}
}
else {
for(int i=0;i<son[now].size();i++) {
ret+=getans(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;
}
bool flag=true;
for(int i=1;i<n;i++) {
if (pro[i]!=pro[1]) {
flag=false;
}
}
if (!flag) {
memset(p,-1,sizeof(p));
for(int i=1;i<n;i++) {
if (pro[i]==1) {
merge(ho[i],i);
}
}
for(int i=1;i<n;i++) {
if (pro[i]==0) {
adj[find(i)].push_back(find(ho[i]));
adj[find(ho[i])].push_back(find(i));
}
}
maketree(0);
memset(dp,-1,sizeof(dp));
return max(getans(0,0),getans(0,1));
}
if (pro[1]==1) {
int ret=0;
for(int i=0;i<n;i++) {
ret+=co[i];
}
return ret;
}
if (pro[1]==2) {
int ret=0;
for(int i=0;i<n;i++) {
ret=max(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:22:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<son[now].size();i++) {
~^~~~~~~~~~~~~~~~
friend.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<son[now].size();i++) {
~^~~~~~~~~~~~~~~~
friend.cpp: In function 'void maketree(int)':
friend.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[v].size();i++) {
~^~~~~~~~~~~~~~
friend.cpp: In function 'int getans(int, int)':
friend.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<son[now].size();i++) {
~^~~~~~~~~~~~~~~~
friend.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<son[now].size();i++) {
~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 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 |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 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 |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 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 |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 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 |
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 |
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 |
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 |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 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 |
512 KB |
Output is correct |
10 |
Correct |
6 ms |
384 KB |
Output is correct |
11 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 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 |
4 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 |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Runtime error |
45 ms |
5240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |