Submission #1092033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092033		Hacv16	Bosses (BOI16_bosses)	C++17	67 / 100	1555 ms	1112 KiB

bosses

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

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

const int MAX = 5e3 + 10;
const int INF = 0x3f3f3f3f;

int n;
vector<int> adj[MAX];

inline int testRoot(int root)
{
	vector<bool> seen(n + 1);
	vector<int> salary(n + 1), processed;
	vector<vector<int>> children(n + 1);

	queue<int> q; q.push(root);
	seen[root] = true;

	while(q.size())
	{
		int u = q.front(); q.pop();
		processed.push_back(u);

		for(auto v : adj[u])
		{
			if(seen[v]) continue;
			seen[v] = true;
			children[u].push_back(v);
			q.push(v);
		}
	}

	for(int i = 1; i <= n; i++)
		if(!seen[i]) return INF;

	int totalCost = 0;
	reverse(processed.begin(), processed.end());

	for(auto curNode : processed)
	{
		int sum = 0;

		for(auto v : children[curNode])
			sum += salary[v];

		salary[curNode] = sum + 1;
		totalCost += salary[curNode];
	}

	return totalCost;
}

int32_t main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	for(int i = 1; i <= n; i++)
	{
		int k; cin >> k;

		while(k--)
		{
			int u; cin >> u;
			adj[u].push_back(i);
		}
	}

	int ans = INF;

	for(int i = 1; i <= n; i++)
		ans = min(ans, testRoot(i));

	cout << ans << '\n';
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33