Submission #1092034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092034		Hacv16	Bosses (BOI16_bosses)	C++14	67 / 100	1591 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 get(void)
{
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    int ret = 0;
    while (c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0'), c = getchar();
    return ret;
}

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)
{
	n = get();

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

		while(k--)
		{
			int u = get();
			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