Submission #764028

#	Time	Username	Problem	Language	Result	Execution time	Memory
764028		SanguineChameleon	Friend (IOI14_friend)	C++17	16 / 100	2 ms	2704 KiB

friend

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

const int maxn = 1e5 + 20;
vector<pair<int, int>> ch[maxn];
int a[maxn];
int dp[maxn][2];

void dfs(int u) {
	for (auto e: ch[u]) {
		int v = e.first;
		dfs(v);
	}
	int sum = a[u];
	for (auto e: ch[u]) {
		int v = e.first;
		int op = e.second;
		if (op == 1) {
			sum += max(dp[v][0], dp[v][1]);
		}
	}
	dp[u][1] = max(dp[u][1], sum);
	sum = 0;
	int sum_all = 0;
	for (auto e: ch[u]) {
		int v = e.first;
		int op = e.second;
		if (op == 1) {
			sum += dp[v][0];
		}
		if (op == 2) {
			dp[u][0] = max(dp[u][0], sum + dp[v][0]);
		}
		if (op == 0) {
			dp[u][0] = max(dp[u][0], sum_all + max(dp[v][0], dp[v][1]));
		}
		sum_all += (op == 0 ? max(dp[v][0], dp[v][1]) : dp[v][0]);
	}
	dp[u][0] = max(dp[u][0], sum);
	sum = 0;
	sum_all = 0;
	for (auto e: ch[u]) {
		int v = e.first;
		int op = e.second;
		if (op == 1) {
			sum += max(dp[v][0], dp[v][1]);
		}
		if (op == 2) {
			dp[u][1] = max(dp[u][1], sum + max(dp[v][0], dp[v][1]));
		}
		if (op == 0) {
			dp[u][1] = max(dp[u][1], sum_all + max(dp[v][0], dp[v][1]));
		}
		sum_all +=  max(dp[v][0], dp[v][1]);
	}
	dp[u][1] = max(dp[u][1], sum);
}

int findSample(int n, int confidence[], int host[], int protocol[]){
	for (int i = 0; i < n; i++) {
		a[i] = confidence[i];
	}
	for (int v = 1; v < n; v++) {
		ch[host[v]].emplace_back(v, protocol[v]);
	}
	for (int i = 0; i < n; i++) {
		sort(ch[i].begin(), ch[i].end());
	}
	dfs(0);
	return max(dp[0][0], dp[0][1]);
}

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