Submission #388157

#	Time	Username	Problem	Language	Result	Execution time	Memory
388157		Nima_Naderi	Bosses (BOI16_bosses)	C++14	100 / 100	774 ms	716 KiB

bosses

//In the name of God
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 5e3 + 10;
const ll INF = 1e18;
ll n, sum, ted;
ll dis[MXN];
vector<ll> adj[MXN];
queue<ll> q;
bool vis[MXN];
ll BFS(ll src){
	memset(dis, 63, sizeof dis), memset(vis, 0, sizeof vis);
	dis[src] = 1, vis[src] = 1;
	q.push(src), sum = 0, ted = 0;
	while(!q.empty()){
		ll u = q.front(); q.pop();
		sum += dis[u], ted ++;
		for(auto v : adj[u]){
			if(!vis[v]){
				vis[v] = 1, dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	//cout << src << ' ' << sum << ' ' << ted << '\n';
	return (ted == n ? sum : INF);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++){
		ll k; cin >> k;
		for(int j = 1, x; j <= k; j ++) cin >> x, adj[x].push_back(i);
	}
	ll ans = INF;
	for(int i = 1; i <= n; i ++) ans = min(ans, BFS(i));
	cout << ans << '\n';
	return 0;
}
//! This is NIMA !

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