oj.uz

Submission #278773

# Submission time Handle Problem Language Result Execution time Memory
278773 2020-08-21T21:06:34 Z amiratou Friend (IOI14_friend) C++14
46 / 100
 41 ms 9720 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],N;
int prot[100005],ho[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];
	}
}
void construct(){
	for (int i = 1; i < N; ++i)
	{
		if(prot[i]==0){
			adj[ho[i]].insert(i);
			adj[i].insert(ho[i]);
		}
		else if(prot[i]==1){
			for(auto it:adj[ho[i]])
				adj[i].insert(it),adj[it].insert(i);
		}
		else{
			adj[ho[i]].insert(i);
			adj[i].insert(ho[i]);
			for(auto it:adj[ho[i]])
				adj[i].insert(it),adj[it].insert(i);	
		}
	}
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	N=n;
	color[0]=-1,conf[0]=confidence[0];
	if(conf[0]!=1)flag3=1;
	for (int i = 1; i < n; ++i)
	{
		prot[i]=protocol[i];
		ho[i]=host[i];
		color[i]=-1;
		conf[i]=confidence[i];
		if(conf[i]!=1)flag3=1;
		if(protocol[i]==0)
			flag0=1;
		else if(protocol[i]==1)
			flag1=1;
		else flag2=1;
	}
	ll ans=0;
	if(n<=10){
		construct();
		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){
		construct();
		solve(0,0);
		ans=max(dp[0][0],dp[0][1]);
	}
	else if(!flag2 && !flag3){
		construct();
		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;
}

Subtask #1
11.0 / 11.0

# 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 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 3 ms 4992 KB Output is correct
13 Correct 4 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 4 ms 4992 KB Output is correct
16 Correct 4 ms 4992 KB Output is correct
17 Correct 4 ms 4992 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 5 ms 5120 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 5120 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 5 ms 5120 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 5 ms 5248 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 3 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 5 ms 5120 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5024 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 5248 KB Output is correct
6 Correct 4 ms 5248 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 5248 KB Output is correct
13 Correct 4 ms 5248 KB Output is correct
14 Correct 4 ms 5120 KB Output is correct
15 Correct 4 ms 5216 KB Output is correct

Subtask #5
0 / 23.0

# 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 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 4 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 -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 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 3 ms 4992 KB Output is correct
6 Correct 4 ms 5120 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 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Incorrect 41 ms 9720 KB Output isn't correct
13 Halted 0 ms 0 KB -