제출 #1316509

#제출 시각아이디문제언어결과실행 시간메모리
1316509danteBosses (BOI16_bosses)C++20
100 / 100
742 ms1036 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e3 + 3;

int n;
ll val[N];
vector<int> boss[N], G[N];
bool vis[N];

ll dfs(int v, int p = -1){
	ll sum = 1;
	for (auto i : G[v]){
		if (i == p) continue;
		sum += dfs(i, v);
	}
	return val[v] = sum;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		int k;
		cin >> k;
		while (k--){
			int x;
			cin >> x;
			boss[x].push_back(i);
		}
	}

	ll ans = LLONG_MAX;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++) {
			vis[j] = 0;
			G[j].clear();
		}


		queue<int> que;
		que.push(i);
		vis[i] = 1;
		int cnt = 1;

		while (!que.empty()){
			int t = que.front();
			que.pop();
			for (auto x : boss[t]){
				if (!vis[x]){
					cnt++;
					G[x].push_back(t);
					G[t].push_back(x);
					que.push(x);
					vis[x] = 1;
				}
			}
		}

		if (cnt != n) continue;
		dfs(i);
		ll can = 0;
		for (int j = 1; j <= n; j++) can += val[j];
		ans = min(can, ans);
	}

	cout << ans << "\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...