Submission #404191

#	Time	Username	Problem	Language	Result	Execution time	Memory
404191		peuch	Friend (IOI14_friend)	C++17	69 / 100	32 ms	2884 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 10;

int dp[MAXN][2];
int v[MAXN];
int cor[MAXN];

int marcB[MAXN];
int match[MAXN];

int marc[MAXN];

vector<int> ar[MAXN];
vector<int> grp[2];

int mask[MAXN];

bool dfs(int cur);
void calc(int cur);

int sub1(int n, int confidence[], int host[], int protocol[]){
	for(int i = 0; i < n; i++)
		v[i] = confidence[i];
	
	for(int i = 1; i < n; i++){
		if(protocol[i] != 1){
			mask[i] |= (1 << host[i]);
			mask[host[i]] |= (1 << i);
		}
		if(protocol[i] != 0){
			for(int j = 0; j < n; j++){
				if((1 << j) & mask[host[i]]) 
					mask[i] |= (1 << j), mask[j] |= (1 << i);
			}
		}
		if(mask[i] & (1 << i)) mask[i] ^= (1 << i);
	}
	if(mask[0] & 1) mask[0] ^= 1;
	
	int ans = 0;
	for(int i = 0; i < (1 << n); i++){
		int auxMask = 0;
		int sum = 0;
		for(int j = 0; j < n; j++)
			if((1 << j) & i) auxMask |= mask[j], sum += v[j];
		if(auxMask & i) continue;
		ans = max(ans, sum);
	}
	return ans;
}

int sub2(int n, int confidence[], int host[], int protocol[]){
	int sum = 0;
	for(int i = 0; i < n; i++)
		sum += confidence[i];
	return sum;
}

int sub3(int n, int confidence[], int host[], int protocol[]){
	int maxi = 0;
	for(int i = 0; i < n; i++)
		maxi = max(confidence[i], maxi);
	return maxi;
}

int sub4(int n, int confidence[], int host[], int protocol[]){
	
	memset(dp, -1, sizeof(dp));
	
	for(int i = 0; i < n; i++)
		v[i] = confidence[i];
	for(int i = 1; i < n; i++)
		ar[host[i]].push_back(i);
 	calc(0);
	return dp[0][1];
}

int sub5(int n, int confidence[], int host[], int protocol[]){
	
	for(int i = 0; i < n; i++)
		v[i] = confidence[i];
	
	grp[0].push_back(0);
	cor[0] = 0;
	for(int i = 1; i < n; i++){
		if(protocol[i] == 0){
			ar[host[i]].push_back(i);
			ar[i].push_back(host[i]);
			cor[i] = !cor[host[i]];
			grp[cor[i]].push_back(i);
		}
		else{
			for(int j = 0; j < ar[host[i]].size(); j++){
				ar[ar[host[i]][j]].push_back(i);
				ar[i].push_back(ar[host[i]][j]);
			}
			cor[i] = cor[host[i]];
			grp[cor[i]].push_back(i);
		}
	}
	
	for(int i = 0; i < n; i++)
		match[i] = -1;
	
	bool flag = true;
	int ans = 0;
	while(flag){
		flag = false;
		for(int i = 0; i < n; i++) marcB[i] = 0;
		for(int i = 0; i < grp[0].size(); i++){
			int cur = grp[0][i];
			if(match[cur] != -1) continue;
			if(dfs(cur)){
				flag = true;
				ans++;
			}		
		}
	}
	ans = n - ans;
	return ans;
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	
	bool caso1 = true;
	bool caso2 = true;
	bool caso3 = true;
	bool caso4 = true;
	bool caso5 = true;
	if(n > 10) caso1 = false;
	for(int i = 1; i < n; i++){
		caso2 &= protocol[i] == 1;
		caso3 &= protocol[i] == 2;
		caso4 &= protocol[i] == 0;
		caso5 &= protocol[i] != 2;
	}
	
	if(caso1) return sub1(n, confidence, host, protocol);
	if(caso2) return sub2(n, confidence, host, protocol); 
	if(caso3) return sub3(n, confidence, host, protocol);
	if(caso4) return sub4(n, confidence, host, protocol);
	if(caso5) return sub5(n, confidence, host, protocol);
}

bool dfs(int cur){
	for(int i = 0; i < ar[cur].size(); i++)	{
		int viz = ar[cur][i];
		if(marcB[viz]) continue;
		marcB[viz] = 1;
		if(match[viz] == -1 || dfs(match[viz])){
			match[cur] = viz;
			match[viz] = cur;
			return true;
		}
	}
	return false;
}

void calc(int cur){
	dp[cur][0] = 0;
	dp[cur][1] = v[cur];
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		calc(viz);
		dp[cur][0] += dp[viz][1];
		dp[cur][1] += dp[viz][0];
	}
	dp[cur][1] = max(dp[cur][1], dp[cur][0]);
}

Compilation message (stderr)

friend.cpp: In function 'int sub5(int, int*, int*, int*)':
friend.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int j = 0; j < ar[host[i]].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0; i < grp[0].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
friend.cpp: In function 'bool dfs(int)':
friend.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for(int i = 0; i < ar[cur].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
friend.cpp: In function 'void calc(int)':
friend.cpp:165:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:146:1: warning: control reaches end of non-void function [-Wreturn-type]
  146 | }
      | ^

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31