Submission #1091934

#TimeUsernameProblemLanguageResultExecution timeMemory
1091934DangKhoizzzzBosses (BOI16_bosses)C++14
100 / 100
518 ms812 KiB
// Meow :3
 
#include <bits/stdc++.h>
#define int long long int
 
using namespace std;
 
const int MAXN = 5e3 + 5;
 
queue <int> q;
 
bool mark[MAXN];
 
vector <int> adj[MAXN];
 
int h[MAXN];
 
int ans = 0;
 
int cnt = 0;
 
void bfs(){
	while(!q.empty()){
		int v = q.front();
		q.pop();
		ans += h[v];
		cnt++;
		for(auto u : adj[v]){
			if(!mark[u]){
				h[u] = h[v] + 1;
				mark[u] = true;
				q.push(u);
			}
		}
	}
}
signed main(){
	int n;
	cin>>n;
	for(int i = 1 ; i <= n ; i++){
		int k;
		cin>>k;
		for(int j = 1 ; j <= k ; j++){
			int x;
			cin>>x;
			adj[x].push_back(i);
		}
	}
	int ANS = 1e18;
	for(int i = 1 ; i <= n ; i++){
		mark[i] = 1;
		q.push(i);
		h[i] = 1;
		bfs();
		memset(mark , 0 , sizeof mark);
		fill(h + 1 , h + n + 1 , 0);
		if(cnt == n) ANS = min(ans , ANS);
		ans = 0;
		cnt = 0;
	}
	cout<<ANS<<endl;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...