제출 #1343543

#제출 시각아이디문제언어결과실행 시간메모리
1343543jumpBosses (BOI16_bosses)C++20
100 / 100
712 ms1036 KiB
#include <bits/stdc++.h>
#define int long long

int n;

std::vector<int> adj[5100];
std::vector<int> child[5100];
int depth[5100];
int total = 0;
int dfs(int curr){
	//std::cout << curr << ' ';
	if(child[curr].empty()){
		total+=1;
		return 1;
	}
	int sum=1;
	for(auto to:child[curr]){
		sum+=dfs(to);
	}
	total+=sum;
	return sum;
}
int bfs(int first){
	total = 0;
	for(int i=0;i<=n;i++){
		depth[i]=0;
		child[i]={};
	}
	std::queue<int> q;
	q.push(first);
	depth[first]=1;
	while(!q.empty()){
		int curr=q.front();q.pop();
		//std::cout << curr << ' ';
		for(auto to:adj[curr]){
			if(depth[to]==0){
				depth[to]=depth[curr]+1;
				child[curr].push_back(to);
				q.push(to);
			}
		}
	}
	for(int i=0;i<n;i++){
		if(depth[i]==0)return 1e9;
	}
	dfs(first);
	//std::cout << '\n';
	return total;
}
signed main() {
	std::cin >> n;
	for(int i=0;i<n;i++){
		int num;
		std::cin >> num;
		for(int j=0;j<num;j++){
			int from;
			std::cin >> from;
			adj[from-1].push_back(i);
		}
	}
	int min = 1e9;
	for(int i=0;i<n;i++){
		int value = bfs(i);
		min=std::min(min,value);
		//std::cout << value << '\n';
	}
	std::cout << min << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...