# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
237637 |
2020-06-08T01:48:34 Z |
urd05 |
Friend (IOI14_friend) |
C++14 |
|
44 ms |
6648 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];
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;
}
bool visited[1000];
bool type[1000];
int num[1000];
vector<int> adj[1000];
vector<int> rev[1000];
int a[1000];
int b[1000];
bool dfs(int v) {
visited[v]=true;
for(int i=0;i<adj[v].size();i++) {
int next=adj[v][i];
if (b[next]==-1||(!visited[b[next]]&&dfs(b[next]))) {
a[v]=next;
b[next]=v;
return true;
}
}
return false;
}
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(a,-1,sizeof(a));
memset(b,-1,sizeof(b));
int as=0;
int bs=0;
for(int i=1;i<n;i++) {
if (pro[i]==0) {
type[i]=!type[ho[i]];
if (!type[i]) {
num[i]=as++;
adj[num[i]].push_back(num[ho[i]]);
rev[num[ho[i]]].push_back(num[i]);
}
else {
num[i]=bs++;
adj[num[ho[i]]].push_back(num[i]);
rev[num[i]].push_back(num[ho[i]]);
}
}
else {
type[i]=type[ho[i]];
if (!type[i]) {
num[i]=as++;
for(int j=0;j<adj[ho[i]].size();j++) {
int nt=adj[ho[i]][j];
adj[num[i]].push_back(nt);
rev[nt].push_back(num[i]);
}
}
else {
num[i]=bs++;
for(int j=0;j<rev[ho[i]].size();j++) {
int nt=rev[ho[i]][j];
adj[nt].push_back(num[i]);
rev[num[i]].push_back(nt);
}
}
}
}
int flow=0;
for(int i=0;i<as;i++) {
if (a[i]==-1) {
memset(visited,0,sizeof(visited));
if (dfs(i)) {
flow++;
}
}
}
return n-flow;
}
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: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++) {
~^~~~~~~~~~~~~~~~
friend.cpp: In function 'bool dfs(int)':
friend.cpp:45: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 findSample(int, int*, int*, int*)':
friend.cpp:148:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adj[ho[i]].size();j++) {
~^~~~~~~~~~~~~~~~~~
friend.cpp:156:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<rev[ho[i]].size();j++) {
~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
512 KB |
Output is correct |
4 |
Correct |
5 ms |
512 KB |
Output is correct |
5 |
Correct |
5 ms |
432 KB |
Output is correct |
6 |
Correct |
5 ms |
384 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 |
512 KB |
Output is correct |
11 |
Correct |
4 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 |
4 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 |
# |
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 |
512 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
512 KB |
Output is correct |
5 |
Correct |
5 ms |
512 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 |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
360 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 |
512 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 |
512 KB |
Output is correct |
13 |
Correct |
5 ms |
512 KB |
Output is correct |
14 |
Correct |
5 ms |
512 KB |
Output is correct |
15 |
Correct |
5 ms |
512 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 |
512 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 |
512 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
5 ms |
512 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 |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
512 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 |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Runtime error |
44 ms |
6648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
13 |
Halted |
0 ms |
0 KB |
- |