Submission #697778

#TimeUsernameProblemLanguageResultExecution timeMemory
697778TranGiaHuy1508Bosses (BOI16_bosses)C++17
0 / 100
1 ms324 KiB
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

int n;
vector<int> vst;
vector<vector<int>> adj, structure;

int total;

int dfs(int x, int p = -1){
	int sum = 0;
	for (auto k: structure[x]){
		if (k == p) continue;
		sum += dfs(k, x);
	}
	total += sum + 1;
	return sum + 1;
}

void main_program(){
	cin >> n;

	adj.resize(n);

	for (int i = 0; i < n; i++){
		int sz; cin >> sz;
		for (int j = 0; j < sz; j++){
			int x; cin >> x; x--;
			adj[x].push_back(i);
		}
	}

	int res = 1e9;

	for (int root = 0; root < n; root++){
		vst.assign(n, 0);
		structure.clear(); structure.resize(n);

		queue<int> q; q.push(root); vst[root] = 1;
		while (!q.empty()){
			int x = q.front(); q.pop();
			for (auto k: adj[x]){
				if (!vst[k]){
					vst[k] = 1;
					structure[x].push_back(k);
					q.push(k);
				}
			}
		}

		total = 0; dfs(root);
		res = min(res, total);
	}

	cout << res << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...