Submission #1328505

#TimeUsernameProblemLanguageResultExecution timeMemory
1328505tkm_algorithmsBosses (BOI16_bosses)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int inf = 1e9;
const int NMAX = 5e3;
int vis[NMAX];

void solve() {
	int n; cin >> n;
	vector<int> g[n+1];
	rep(i, 1, n+1) {
		int x; cin >> x;
		while (x--) {
			int y; cin >> y;
			g[y].push_back(i);
		}
	}
	
	int res = inf;
	rep(i, 1, n+1) { // potential root
		memset(vis, 0, sizeof vis);
		queue<P> q; vis[i] = 1;
		q.push({i, 0}); int sm = 0;
		while (!q.empty()) {
			auto [nd, d] = q.front(); q.pop();
			sm += d;
			for (auto j: g[nd])
				if (!vis[j])
					vis[j] = 1, q.push(P(j, d+1));
		}
		res = min(res, sm);
	}
	cout << res+n << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...