Submission #78755

#	Time	Username	Problem	Language	Result	Execution time	Memory
78755		scanhex	Bosses (BOI16_bosses)	C++17	100 / 100	723 ms	1388 KiB

bosses

#include <bits/stdc++.h>

using namespace std;
using nagai = long long;
using ll = long long;

const int N = 5000;
vector<int> g[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int k;
		cin >> k;
		for (int j = 0; j < k; ++j)
		{
			 int x;
			 cin >> x;
			 --x;
			 g[x].push_back(i);
		}
	}
	int ans = 1e9;
	for (int rt = 0; rt < n; ++rt)
	{
		vector<int> d(n, -1);
		d[rt] = 1;
		vector<int> q = {rt};
		for (int i = 0; i < q.size(); ++i)
		{
			 int x = q[i];
			 for (int y : g[x])
			 {
				  if (d[y] == -1)
					  d[y] = d[x] + 1, q.push_back(y);
			 }
		}
		if (count(d.begin(), d.end(), -1))
			continue;
		ans = min(ans, accumulate(d.begin(), d.end(), 0));
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < q.size(); ++i)
                   ~~^~~~~~~~~~

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