Submission #695225

#	Time	Username	Problem	Language	Result	Execution time	Memory
695225		Cyber_Wolf	Bosses (BOI16_bosses)	C++17	100 / 100	747 ms	684 KiB

bosses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


const lg N = 5e3+5;

vector<lg> adj[N];
lg vis[N], tmp, dist[N], n;

lg bfs(lg src, lg par = -1)
{
	queue<lg> q;
	q.push(src);
	vis[src] = tmp;
	memset(dist, 0, sizeof(dist));
	lg dis = 1;
	while(q.size())
	{
		lg sz = q.size();
		dis++;
		while(sz--)
		{
			lg u = q.front();
			q.pop();
			for(auto it : adj[u])
			{
				if(vis[it] == tmp)	continue;
				q.push(it);
				vis[it] = tmp;
				dist[it] = dis;
			}	
		}
	}
	lg x = 1; 
	for(int i = 1; i <= n; i++)
	{
		x &= (vis[i] == tmp);
	}
	if(!x)	return 1e18;
	lg ans = 1;
	for(int i = 1; i <= n; i++)	ans += dist[i];
	return ans;
}

int main()
{
	fastio;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		lg x;
		cin >> x;
		while(x--)
		{
			lg y;
			cin >> y;
			adj[y].push_back(i);
		}
	}
	lg ans = 1e18;
	for(int i = 1; i <= n; i++)
	{
		tmp++;
		lg cur = bfs(i);
		// cout << i << ' ' << cur << '\n';
		ans = min(ans, cur);
	}
	cout << ans << '\n';
	

    return 0;
}

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