Submission #385855

#	Time	Username	Problem	Language	Result	Execution time	Memory
385855		ParsaAlizadeh	Friend (IOI14_friend)	C++17	46 / 100	31 ms	1516 KiB

friend

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

int Sub1(int n, int confidence[], int host[], int protocol[]) {
	vector<vector<bool>> g(n, vector<bool>(n, false));
	auto add_edge = [&g] (int u, int v) {
		g[u][v] = g[v][u] = true;
	};
	for (int i = 1; i < n; i++) {
		if (protocol[i] == 0 || protocol[i] == 2) {
			add_edge(i, host[i]);
		}
		if (protocol[i] == 1 || protocol[i] == 2) {
			for (int j = 0; j < n; j++) if (g[host[i]][j]) {
				add_edge(j, i);
			}
		}
	}
	int ans = -1;
	for (int mask = 0; mask < (1 << n); mask++) {
		bool flag = true;
		int now = 0;
		for (int i = 0; i < n; i++) if (mask & (1 << i)) {
			now += confidence[i];
			for (int j = i + 1; j < n; j++) if (mask & (1 << j)) {
				flag &= !g[i][j];
			}
		}
		if (!flag)
			continue;
		ans = max(ans, now);
	}
	return ans;
}

int Sub2(int n, int confidence[], int host[], int protocol[]) {
	int ans = confidence[0];
	for (int i = 1; i < n; i++) {
		if (protocol[i] != 1)
			return -1;
		ans += confidence[i];
	}
	return ans;
}

int Sub3(int n, int confidence[], int host[], int protocol[]) {
	int ans = confidence[0];
	for (int i = 1; i < n; i++) {
		if (protocol[i] != 2)
			return -1;
		ans = max(ans, confidence[i]);
	}
	return ans;
}

int Sub4(int n, int confidence[], int host[], int protocol[]) {
	for (int i = 1; i < n; i++) {
		if (protocol[i] != 0)
			return -1;
	}
	vector<vector<int>> adj(n), dp(n, vector<int>(2));
	for (int i = 1; i < n; i++)
		adj[host[i]].push_back(i);
	for (int i = n; i--;) {
		dp[i][1] = confidence[i];
		for (int j : adj[i]) {
			dp[i][0] += dp[j][1];
			dp[i][1] += dp[j][0];
		}
		dp[i][1] = max(dp[i][1], dp[i][0]);
	}
	return dp[0][1];
}

int findSample(int n, int confidence[], int host[], int protocol[]){
	int ans = -1;
	if (n <= 10)
		return Sub1(n, confidence, host, protocol);
	if ((ans = Sub2(n, confidence, host, protocol)) != -1)
		return ans;
	if ((ans = Sub3(n, confidence, host, protocol)) != -1)
		return ans;
	if ((ans = Sub4(n, confidence, host, protocol)) != -1)
		return ans;
	return -1;
}

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