Submission #1352870

#TimeUsernameProblemLanguageResultExecution timeMemory
1352870kl0989eBosses (BOI16_bosses)C++20
100 / 100
339 ms736 KiB
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=5010;

vector<vi> graph(maxn);
vi seen(maxn);

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
	cin >> n;
	int k,a;
	for (int i=0; i<n; i++) {
		cin >> k;
		for (int j=0; j<k; j++) {
			cin >> a;
			graph[--a].pb(i);
		}
	}
	int ans=1e9;
	for (int i=0; i<n; i++) {
		fill(all(seen),0);
		queue<int> q;
		q.push(i);
		seen[i]=1;
		int t=0;
		int cnt=0;
		while (q.size()) {
			int cur=q.front();
			q.pop();
			cnt++;
			t+=seen[cur];
			for (auto to:graph[cur]) {
				if (!seen[to]) {
					seen[to]=seen[cur]+1;
					q.push(to);
				}
			}
		}
		if (cnt==n) {
			ans=min(ans,t);
		}
	}
	cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...