제출 #58579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58579		aome	친구 (IOI14_friend)	C++17	11 / 100	45 ms	1848 KiB

friend

#include "friend.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;
const int INF = 1e9;

int n;
int mx;
int res;
int a[N];
int h[N];
int f[N][16];
bool e[N][4];
bool visit[N];
vector<int> G[N];

void add(int u, int v) {
	G[u].push_back(v), G[v].push_back(u);
}

void dfs(int u) {
	visit[u] = 1;
	for (auto v : G[u]) {
		if (!visit[v]) {
			h[v] = h[u] + 1, dfs(v);
		}
		else if (h[u] > h[v]) {
			e[u][h[u] - h[v]] = 1;
		}
	}
}

void solve(int u) {
	visit[u] = 1;
	for (int i = 0; i < 16; ++i) {
		if (i & 1) f[u][i] = a[u];
		for (int j = 1; j < 4; ++j) {
			if ((i & 1) && (i >> j & 1) && e[u][j]) {
				f[u][i] = -INF; break;
			}
		}
	}
	for (auto v : G[u]) {
		if (visit[v]) continue;
		solve(v);
		for (int j = 0; j < 16; ++j) {
			int mask = (j << 1) & 15;
			int tmp = max(f[v][mask], f[v][mask + 1]);
			f[u][j] = max(-INF, f[u][j] + tmp);
		}
	}
	for (int i = 0; i < 16; ++i) mx = max(mx, f[u][i]);
}

int brute() {
	int res = -INF;
	for (int i = 0; i < (1 << n); ++i) {
		bool fail = 0;
		for (int j = 0; j < n; ++j) {
			for (auto k : G[j]) {
				if ((i >> j & 1) && (i >> k & 1)) fail = 1;
			}
		}
		if (fail) continue;
		int sum = 0;
		for (int j = 0; j < n; ++j) {
			if (i >> j & 1) sum += a[j];
		}
		res = max(res, sum);
	}
	return res;
}

int findSample(int _n, int confidence[], int host[], int protocol[]) {
	n = _n;
	if (n > 1000) return 0;
	for (int i = 0; i < n; ++i) {
		a[i] = confidence[i];
	}
	for (int i = 1; i < n; ++i) {
		if (protocol[i] == 0) {
			add(host[i], i);
		}
		if (protocol[i] == 1) {
			for (auto j : G[host[i]]) add(i, j);
		} 
		if (protocol[i] == 2) {
			for (auto j : G[host[i]]) add(i, j);
			add(host[i], i);
		} 
	}
	if (n > 10) return 0;
	return brute();
	// for (int i = 0; i < n; ++i) {
	// 	if (!visit[i]) dfs(i);
	// }
	// memset(visit, 0, sizeof visit);
	// for (int i = 0; i < n; ++i) {
	// 	if (visit[i]) continue;
	// 	mx = -INF, solve(i), res += mx;
	// }
	// return res;
}

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