제출 #927925

#제출 시각아이디문제언어결과실행 시간메모리
927925TAhmed33Bosses (BOI16_bosses)C++98
100 / 100
844 ms1116 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
int n;
vector <int> adj[5001];
int dp[5001] = {};
int d = 0;
bool vis[5001];
vector <int> newadj[5001];
void calc (int pos) {
	dp[pos] = 1;
	d++;
	for (auto j : newadj[pos]) {
		calc(j);
		dp[pos] += dp[j];
	}
}
signed main () {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		while (x--) {
			int y;
			cin >> y;
			adj[y].push_back(i);
		}
	}
	int ans = 1e9;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			dp[j] = 0;
			vis[j] = 0;
			newadj[j].clear();
		}
		queue <int> cur;
		cur.push(i);
		vis[i] = 1;
		while (!cur.empty()) {
			int l = cur.front();
			cur.pop();
			for (auto j : adj[l]) {
				if (!vis[j]) {
					vis[j] = 1;
					newadj[l].push_back(j);
					cur.push(j);
				}
			}
		}
		d = 0;
		calc(i);
		if (d != n) continue;
		int y = 0;
		for (int j = 1; j <= n; j++) {
			y += dp[j];
		}
		if (ans > y) ans = y;
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...