Submission #1278675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278675		Johann	친구 (IOI14_friend)	C++20	0 / 100	72 ms	131072 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;
}

int sub4(int n, int confidence[], int host[], int protocol[])
{
	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 find_augmenting_path(vvi &adj, int v, vi &matching)
{
	for (int u : adj[v])
	{
		if (matching[u] == v)
			continue;
		if (matching[u] == -1 || find_augmenting_path(adj, matching[u], matching))
		{
			matching[u] = v;
			matching[v] = u;
			return 1;
		}
	}
	return 0;
}

int sub5(int n, int confidence[], int host[], int protocol[])
{
	vvi adj(n);
	vi side(n);
	side[0] = 0;
	for (int t = 1; t < n; ++t)
	{
		int h = host[t];
		if (protocol[t] == 1) // My
		{
			for (int u : adj[h])
				adj[u].push_back(t), adj[t].push_back(u);
			side[t] = side[h];
		}
		if (protocol[t] == 0) // I
		{
			adj[h].push_back(t), adj[t].push_back(h);
			side[t] = 1 - side[h];
		}
	}
	vi matching(n, -1);
	for (int i = 0; i < n; ++i)
	{
		int should_break = true;
		for (int u = 0; u < n; ++u)
		{
			if (side[u] == 0 && matching[u] == -1)
				should_break |= find_augmenting_path(adj, u, matching);
		}
		if (should_break)
			break;
	}

	vi vis(n, 0);
	stack<int> st;
	for (int i = 0; i < n; ++i)
		if (side[i] == 0 && matching[i] == -1)
			st.push(i);
	while (!st.empty())
	{
		int v = st.top();
		st.pop();
		if (vis[v])
			continue;
		vis[v] = 1;
		for (int u : adj[v])
		{
			assert(matching[u] != -1);
			vis[u] = 1;
			st.push(matching[u]);
		}
	}

	int ans = n;
	for (int i = 0; i < n; ++i)
	{
		if (side[i] == 0)
		{
			if (vis[i] == 0)
				--ans;
		}
		else
		{
			if (vis[i] == 1)
				--ans;
		}
	}
	return ans;
}

// 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
	// return sub4(n, confidence, host, protocol);
	// subtask 5: I and My -> G is bipartite -> size of max independent set
	return sub5(n, confidence, host, protocol);

	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: 0 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31