Submission #1121371

#TimeUsernameProblemLanguageResultExecution timeMemory
1121371heeyBosses (BOI16_bosses)C++14
100 / 100
554 ms848 KiB
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define mod 1'000'000'007
#define inf 1'000'000'000'000'00
#define pb push_back
#define vvi vector<vi>
#define fst cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<vector<int>> a(n);
	vector<int> v(n);
	vector<bool> m(n);
	for(int i = 0; i < n; i++){
		int k; cin >> k;
		for(int j = 0; j < k; j++){
			int p; cin >> p;
			a[p-1].pb(i);
		}
	}
	
	auto bfs = [&](int& r) -> int
	{
		fill(all(v), 0);
		fill(all(m), false);

		queue<int> q;
		q.push(r);
		v[r] = 1;
		m[r] = true;
		while(!q.empty()){
			int c = q.front();
			q.pop();
			for(int &i : a[c]){
				if(!m[i]){
					m[i] = true;
					v[i] = v[c]+1;
					q.push(i);
				}
			}
		}
		int res = 0;
		for(int i = 0; i < n; i++){
			if(!m[i]) return inf;
			res += v[i];
		}
		return res;
	};

	int rez = inf;
	for(int i = 0; i < n; i++) rez = min(rez, bfs(i));
	cout << rez;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...