Submission #416442

#	Time	Username	Problem	Language	Result	Execution time	Memory
416442		mjhmjh1104	Friend (IOI14_friend)	C++17	35 / 100	1 ms	460 KiB

friend

#include "friend.h"
#include <vector>
#include <algorithm>
using namespace std;

int c[1006], dp[1006][2];
vector<int> adj[1006];

int dfs(int x, int y, int prev = -1) {
	if (dp[x][y] + 1) return dp[x][y];
	dp[x][y] = 0;
	if (y) dp[x][y] += c[x];
	for (auto &i: adj[x]) if (i != prev) {
		if (y) dp[x][y] += dfs(i, 0, x);
		else dp[x][y] += max(dfs(i, 0, x), dfs(i, 1, x));
	}
	return dp[x][y];
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
	fill(dp[0], dp[1005] + 2, -1);
	for (int i = 0; i < n; i++) c[i] = confidence[i];
	if (protocol[1] == 1) {
		int res = 0;
		for (int i = 0; i < n; i++) res += confidence[i];
		return res;
	} else if (protocol[1] == 2) {
		int res = 0;
		for (int i = 0; i < n; i++) res = max(res, confidence[i]);
		return res;
	} else {
		for (int i = 1; i < n; i++) {
			adj[i].push_back(host[i]);
			adj[host[i]].push_back(i);
		}
		return max(dfs(0, 0), dfs(0, 1));
	}
}

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