# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
278770 |
2020-08-21T20:59:44 Z |
amiratou |
Friend (IOI14_friend) |
C++14 |
|
253 ms |
47096 KB |
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int> adj[100005];
ll dp[100005][2],conf[100005],color[100005];
bool flag0,flag1,flag2,flag3;
// Find out best sample
void solve(int node,int p){
dp[node][1]=conf[node];
for(auto it:adj[node]){
if(it==p)continue;
solve(it,node);
dp[node][0]+=max(dp[it][0],dp[it][1]);
dp[node][1]+=dp[it][0];
}
}
int findSample(int n,int confidence[],int host[],int protocol[]){
color[0]=-1,conf[0]=confidence[0];
if(conf[0]!=1)flag3=1;
for (int i = 1; i < n; ++i)
{
color[i]=-1;
conf[i]=confidence[i];
if(conf[i]!=1)flag3=1;
if(protocol[i]==0){
flag0=1;
adj[host[i]].insert(i);
adj[i].insert(host[i]);
}
else if(protocol[i]==1){
flag1=1;
for(auto it:adj[host[i]])
adj[i].insert(it),adj[it].insert(i);
}
else{
flag2=1;
adj[host[i]].insert(i);
adj[i].insert(host[i]);
for(auto it:adj[host[i]])
adj[i].insert(it),adj[it].insert(i);
}
}
ll ans=0;
if(!n){
for (int mask = 0; mask < (1<<n); ++mask)
{
vector<int> vec;
ll sum=0;
bool f=1;
for (int j = 0; j < n; ++j)
{
if((mask>>j) &1){
for(auto it:vec)
if(adj[it].find(j)!=adj[it].end()){f=0;break;}
if(!f)break;
sum+=confidence[j],vec.push_back(j);
}
}
if(f)ans=max(ans,sum);
}
}
else if(!flag0 && !flag1){
for (int i = 0; i < n; ++i)
ans=max(ans,(ll)confidence[i]);
}
else if(!flag0 && !flag2){
for (int i = 0; i < n; ++i)
ans+=confidence[i];
}
else if(!flag1 && !flag2){
solve(0,0);
ans=max(dp[0][0],dp[0][1]);
}
else if(!flag2 && !flag3){
for (int i = 0; i < n; ++i)
if(color[i]==-1){
//cerr<<i<<"\n";
int a=0,b=0;
queue<int> q;
q.push(i);
color[i]=0;
while(!q.empty()){
int f=q.front();
q.pop();
if(!color[f])a++;
else b++;
for(auto it:adj[f]){
if(color[it]!=-1)assert(color[it]!=color[f]);
else color[it]=1-color[f],q.push(it);
}
}
//cerr<<a<<","<<b<<"\n";
ans+=max(a,b);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
4992 KB |
Output is correct |
6 |
Correct |
4 ms |
4992 KB |
Output is correct |
7 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
4 ms |
4992 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
4 ms |
4992 KB |
Output is correct |
7 |
Correct |
4 ms |
4992 KB |
Output is correct |
8 |
Correct |
4 ms |
5120 KB |
Output is correct |
9 |
Correct |
4 ms |
5120 KB |
Output is correct |
10 |
Correct |
4 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
13688 KB |
Output is correct |
2 |
Runtime error |
253 ms |
47096 KB |
Memory limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
5120 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
5248 KB |
Output is correct |
6 |
Correct |
4 ms |
5248 KB |
Output is correct |
7 |
Correct |
5 ms |
5024 KB |
Output is correct |
8 |
Correct |
4 ms |
5120 KB |
Output is correct |
9 |
Correct |
4 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
5120 KB |
Output is correct |
11 |
Correct |
5 ms |
5120 KB |
Output is correct |
12 |
Correct |
4 ms |
5120 KB |
Output is correct |
13 |
Correct |
4 ms |
5120 KB |
Output is correct |
14 |
Correct |
4 ms |
5120 KB |
Output is correct |
15 |
Correct |
4 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
4992 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
4 ms |
4992 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
3 ms |
4992 KB |
Output is correct |
8 |
Correct |
3 ms |
4992 KB |
Output is correct |
9 |
Correct |
4 ms |
5248 KB |
Output is correct |
10 |
Correct |
4 ms |
5120 KB |
Output is correct |
11 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
3 ms |
4992 KB |
Output is correct |
3 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |