Submission #1092146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092146		Hacv16	Bosses (BOI16_bosses)	C++17	100 / 100	470 ms	768 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<int> salary(n + 1);
	queue<int> q; q.push(root);

	int totalCost = 0;
	salary[root] = 1;

	while(q.size())
	{
		int u = q.front(); q.pop();
		totalCost += salary[u];

		for(auto v : adj[u])
		{
			if(salary[v]) continue;
			salary[v] = salary[u] + 1;
			q.push(v);
		}
	}

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

	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: 33 / 33