Submission #1268909

#TimeUsernameProblemLanguageResultExecution timeMemory
1268909WH8Bosses (BOI16_bosses)C++20
100 / 100
379 ms1072 KiB
#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);


int32_t main(){
	FASTIO
	int n; cin >> n;
	vector<vi> p(n+1);
	vector<vi> c(n+1);
	int mustbe = 0;
	iloop(1, n+1){
		int k; cin >> k;
		if (k == 0) mustbe = i;
		
		jloop(0, k){
			int cur; cin >> cur;
			p[i].pb(cur);
			c[cur].pb(i);
		}
	}
	int ans = INT_MAX;
	int d[n+1];
	jloop(1, n+1){
		int root = j;
		iloop(0, n+1) d[i] = 0;
		int vis = 1;
		d[root] = 1;
		int cans = 1;
		queue<int> q;
		q.push(root);
		while (!q.empty()){
			int cur = q.front(); q.pop();
			for (auto it : c[cur]){
				if (d[it] != 0) continue;
				vis++;
				q.push(it);
				cans += d[cur] + 1;
				d[it] = d[cur] + 1;
			}
		}
		if (vis != n) continue;
		//cout << "ROOT IS " << root << endl;
		//cout << "CANS IS " << cans << endl;
		if (mustbe == j){
			cout << cans;
			return 0;
		}
		ans = min(ans, cans);
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...