Submission #1243854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243854		wedonttalkanymore	Bosses (BOI16_bosses)	C++20	0 / 100	1 ms	776 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
int n, k;
vector <int> adj[5005];
int length[5005], depth[5005];
struct item
{
	int u, now;
	bool operator <(const item &other) const
	{
		return now > other.now;
	}
};
int ans = 1e18;
void dijk(int u)
{
	for (int i = 1; i <= n; i++)
	{
		length[i] = 0;
		depth[i] = 0;
	}
	length[u] = 1;
	depth[u] = 1;
	queue <int> q;
	q.push(u);
	while(q.size())
	{
		auto tmp = q.front();
		q.pop();
		for (auto v : adj[tmp])
		{
			if (depth[v]) continue;
			depth[v] = depth[tmp] + 1;
			length[v] = length[tmp] + 1;
			q.push(v);
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		if (length[i] == 0) return;
		sum += length[i];
	}
	ans = min(ans, sum);
}
signed main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		int sz;
		cin >> sz;
		for (int j = 1; j <= sz; j++)
		{
			int x;
			cin >> x;
			adj[x].push_back(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		dijk(i);
	}
	cout << ans;
	return 0;
}

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