Submission #350854

#TimeUsernameProblemLanguageResultExecution timeMemory
350854Parsa_PGBosses (BOI16_bosses)C++14
100 / 100
911 ms896 KiB
/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
 
using namespace std;
 
const int maxn = 5e3 + 10, Maxn = 1e5 + 10, SQ = 360 , lg = 22 ; 
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;

vector<int>adj1[maxn] , adj[maxn];
int h[maxn] , val[maxn] , n;
bool vis[maxn];

int bfs(int s){
	for(int i =  0 ;i  < n; i++){
		h[i] = 0;
		vis[i] =0;
		adj[i].clear();
		val[i] = 0;
	}
	queue<int>q;
	q.push(s);
	vis[s] = 1;
	h[s] = 1;
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(auto u : adj1[v]){
			if(!vis[u]){
				q.push(u);
				vis[u] = 1;
				h[u] = h[v] + 1;
			}
		}
	}
	int res = 0;
	for(int i = 0 ; i < n ; i++){
		if(h[i] == 0)
			return inf;
		res += h[i];
	}
	return res;
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0 ; i < n ; i ++){
		int k;
		cin >> k;
		for(int j = 0 ; j < k ; j++){
			int u;
			cin >> u;
			u--;
			adj1[u].pb(i);
		}
	}
	int ans = inf;
	for(int i = 0 ; i < n ; i++){
		ans = min(ans , bfs(i));
	}
	cout << ans << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...