Submission #946295

#	Time	Username	Problem	Language	Result	Execution time	Memory
946295		parsadox2	Bosses (BOI16_bosses)	C++17	100 / 100	392 ms	848 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10;
int n , dis[N] , ans;
vector <int> adj[N];
bool marked[N];

void Solve(int star)
{
	for(int i = 1 ; i <= n ; i++)
		marked[i] = false;
	queue <int> q;
	marked[star] = true;
	dis[star] = 1;
	q.push(star);
	int cnt = n , tmp = 0;
	while(!q.empty())
	{
		int v = q.front();  q.pop();
		tmp += dis[v];
		cnt--;
		for(auto u : adj[v])  if(!marked[u])
		{
			marked[u] = true;
			q.push(u);
			dis[u] = dis[v] + 1;
		}
	}
	if(cnt == 0)
		ans = min(ans , tmp);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	{
		int k;  cin >> k;
		while(k--)
		{
			int x;  cin >> x;
			adj[x].push_back(i);
		}
	}
	ans = N * N;
	for(int i = 1 ; i <= n ; i++)
		Solve(i);
	cout << ans << '\n';
	return 0;
}

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