Submission #1278663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278663		Johann	Friend (IOI14_friend)	C++20	100 / 100	15 ms	1924 KiB

friend

#include "friend.h"

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

#define sz(x) (int)(x.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

void dfs(int v, int p, vvi &adj, vvi &mxt, const int C[])
{
	mxt[v][1] = C[v];
	for (int u : adj[v])
	{
		if (u == p)
			continue;
		dfs(u, v, adj, mxt, C);
		mxt[v][0] += max(mxt[u][0], mxt[u][1]);
		mxt[v][1] += mxt[u][0];
	}
}

// subtask bruteforce
int bruteforce(int n, int confidence[], int host[], int protocol[])
{
	vi forbidden;
	vvi adj(n);
	for (int t = 1; t < n; ++t)
	{
		int h = host[t];
		if (protocol[t] == 1 || protocol[t] == 2) // My & We
			for (int u : adj[h])
			{
				adj[u].push_back(t), adj[t].push_back(u);
				assert(u != t);
				forbidden.push_back((1 << u) + (1 << t));
			}
		if (protocol[t] == 0 || protocol[t] == 2) // I & We
		{
			adj[h].push_back(t), adj[t].push_back(h);
			assert(t != h);
			forbidden.push_back((1 << h) + (1 << t));
		}
	}
	int maxres = 0;
	for (int bitmask = 0; bitmask < (1 << n); ++bitmask)
	{
		bool bad = false;
		for (int f : forbidden)
			if ((f & bitmask) == f)
			{
				bad = true;
				break;
			}
		if (bad)
			continue;

		int res = 0;
		for (int i = 0; i < n; ++i)
			if (bitmask & (1 << i))
				res += confidence[i];
		maxres = max(res, maxres);
	}
	return maxres;
}

// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[])
{
	// if (n <= 10)
	//		return bruteforce(n, confidence, host, protocol);

	vi C(n);
	// copy(confidence, confidence + n, C.begin());
	// subtaks 2: only my friends are your friends -> independent set!
	// int sum = accumulate(confidence, confidence + n, 0);
	// subtask 3: only we are your friends -> complete graph
	// int maxi = *max_element(confidence, confidence + n);
	// subtask 4: only I am your friend -> tree dp
	/*
	vvi adj(n);
	for (int t = 1; t < n; ++t)
	{
		adj[host[t]].push_back(t);
		adj[t].push_back(host[t]);
	}
	vvi max_subtree(n, vi(2, 0)); // max subtree without and with corresponding root
	dfs(0, 0, adj, max_subtree, confidence);
	return max(max_subtree[0][0], max_subtree[0][1]);
	*/

	int ans = 0;
	for (int t = n - 1; t > 0; --t)
	{
		if (protocol[t] == 0)
		{
			// I
			confidence[host[t]] = max(0, confidence[host[t]] - confidence[t]);
			ans += confidence[t];
		}
		else if (protocol[t] == 1)
		{
			// My
			confidence[host[t]] += confidence[t];
		}
		else
		{
			// We
			confidence[host[t]] = max(confidence[host[t]], confidence[t]);
		}
	}
	ans += confidence[0];

	return ans;
}

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