제출 #589378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589378		AlperenT	친구 (IOI14_friend)	C++17	46 / 100	25 ms	4556 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

using namespace std;

const int N = 1000 + 5;

int dp[N][2], ans = 0, onecnt, zerocnt, color[N];

vector<int> graph[N];

bool vis[N];

void gengraph(int n, int host[], int protocol[]){
	for(int i = 1; i < n; i++){
		if(protocol[i] == 0){
			graph[host[i]].push_back(i);
			graph[i].push_back(host[i]);
		}
		else if(protocol[i] == 1){
			for(auto e : graph[host[i]]){
				graph[e].push_back(i);
				graph[i].push_back(e);
			}
		}
		else if(protocol[i] == 2){
			for(auto e : graph[host[i]]){
				graph[e].push_back(i);
				graph[i].push_back(e);
			}
			graph[host[i]].push_back(i);
			graph[i].push_back(host[i]);
		}
	}
}

void dfs(int v, int confidence[]){
	vis[v] = true;

	dp[v][1] = confidence[v];

	for(auto e : graph[v]){
		if(!vis[e]){
			dfs(e, confidence);

			dp[v][1] += dp[e][0];
			dp[v][0] += max(dp[e][0], dp[e][1]);
		}
	}
}

void colorgraph(int v, int c){
	vis[v] = true;
	color[v] = c;

	if(c == 1) onecnt++;
	else zerocnt++;

	for(auto e : graph[v]){
		if(!vis[e]) colorgraph(e, c ^ 1);
	}
}

int findSample(int n, int confidence[], int host[], int protocol[]){
	memset(vis, 0, sizeof(vis));
	memset(dp, 0, sizeof(dp));

	if(n <= 10){ // Subtask 1
		gengraph(n, host, protocol);

		for(int m = 0; m < (1 << n); m++){
			bool flag = true;
			int curans = 0;

			for(int i = 0; i < n; i++){
				if(m & (1 << i)){
					curans += confidence[i];

					for(auto e : graph[i]){
						if(m & (1 << e)) flag = false;
					}
				}
			}

			if(flag) ans = max(ans, curans);
		}

		return ans;
	}
	else if(count(protocol + 1, protocol + n, 1) == n - 1){ // Subtask 2
		return accumulate(confidence, confidence + n, 0);
	}
	else if(count(protocol + 1, protocol + n, 2) == n - 1){ // Subtask 3
		return *max_element(confidence, confidence + n);
	}
	else if(count(protocol + 1, protocol + n, 0) == n - 1){ // Subtask 4
		gengraph(n, host, protocol);

		dfs(0, confidence);

		return max(dp[0][0], dp[0][1]);
	}
	else{ // Subtask 5
		gengraph(n, host, protocol);

		for(int i = 0; i < n; i++){
			if(!vis[i]){
				onecnt = zerocnt = 0;

				colorgraph(i, 0);

				ans += max(onecnt, zerocnt);
			}
		}

		for(int i = 0; i < n; i++){
			for(auto e : graph[i]){
				assert(color[i] != color[e]);
			}
		}

		return ans;
	}
}

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