Submission #1328159

#TimeUsernameProblemLanguageResultExecution timeMemory
1328159crispxxBosses (BOI16_bosses)C++20
100 / 100
460 ms756 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int inf = 1e9 + 5;

void solve() {
	int n; cin >> n;
	
	vector<vector<int>> adj(n);
	
	for(int i = 0; i < n; i++) {
		int k; cin >> k;
		
		for(int j = 0; j < k; j++) {
			int x; cin >> x;
			x--;
			
			adj[x].push_back(i);
		}
	}
	
	int res = inf;
	
	for(int i = 0; i < n; i++) {
		queue<array<int, 2>> q;
		
		q.push({i, 0});
		
		vector<int> used(n);
		
		used[i] = true;
		
		vector<int> dep(n);
		
		int mxd = 0;
		
		// cout << '\n';
		
		// cout << i + 1 << ": " << '\n';
		
		while(!q.empty()) {
			auto [v, d] = q.front();
			q.pop();
			
			// cout << v + 1 << ' ';
			
			dep[d]++;
			
			mxd = d;
			
			for(auto to : adj[v]) {
				if(!used[to]) {
					used[to] = true;
					q.push({to, d + 1});
				}
			}
		}
		
		// cout << '\n';
		
		// for(int j = 0; j < n; j++) {
			// cout << used[j] << ' ';
		// }
		// cout << '\n';
		
		// for(int j = 0; j < n; j++) {
			// cout << dep[j] << ' ';
		// }
		// cout << '\n';
		
		// cout << mxd << '\n';
		
		int ans = n * (mxd + 1), cur = 0;
		
		for(int j = 0; j < mxd; j++) {
			cur += dep[j];
			ans -= cur;
		}
		
		if(accumulate(used.begin(), used.end(), 0) == n) {
			res = min(res, ans);
		}
	}
	
	cout << res << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...