Submission #538221

#TimeUsernameProblemLanguageResultExecution timeMemory
538221amunduzbaevBosses (BOI16_bosses)C++17
100 / 100
670 ms628 KiB
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 5005;
vector<int> edges[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> k(n+1);
	for(int i=1;i<=n;i++){
		cin>>k[i];
		for(int j=0;j<k[i];j++){
			int x; cin>>x;
			edges[x].push_back(i);
		}
	}
	
	int res = n * n;
	for(int i=1;i<=n;i++){
		vector<int> d(n+1, n);
		queue<int> q; q.push(i);
		d[i] = 0;
		while(!q.empty()){
			int i=q.front(); q.pop();
			for(auto x : edges[i]){
				if(d[x] > d[i] + 1){
					d[x] = d[i] + 1;
					q.push(x);
				}
			}
		}
		
		bool ok = 1;
		int rr = n;
		for(int j=1;j<=n;j++){
			if(d[j] == n) ok = 0;
			rr += d[j];
		}
		
		if(ok) res = min(res, rr);
	}
	
	cout<<res<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...