Submission #418179

#	Time	Username	Problem	Language	Result	Execution time	Memory
418179		ja_kingy	Friend (IOI14_friend)	C++14	100 / 100	50 ms	7420 KiB

friend

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

int findSample(int n,int confidence[],int host[],int protocol[]){
	vector<vector<int>> t(n);
	vector<int[2]> dp(n);
	for (int i = 1; i < n; ++i) {
		t[host[i]].push_back(i);
	}
	for (int i = n; i--;) {
		for (int f = 0; f < 2; ++f) {
			int sm = 0;
			for (int v: t[i]) {
				if (protocol[v] == 0) sm += dp[v][1];
				else sm += dp[v][0];
			}
			dp[i][f] = max(dp[i][f], sm);
			for (int v: t[i]) {
				if (protocol[v] == 0) sm += dp[v][0] - dp[v][1];
				else if (f) sm += dp[v][1] - dp[v][0];
				dp[i][f] = max(dp[i][f], sm);
				if (f && protocol[v] == 2) sm += dp[v][0] - dp[v][1];
			}
			if (f) sm += confidence[i];
			dp[i][f] = max(dp[i][f], sm);
		}
	}
	return dp[0][1];
}

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