Submission #287840

#	Time	Username	Problem	Language	Result	Execution time	Memory
287840		nandonathaniel	Bosses (BOI16_bosses)	C++14	100 / 100	1478 ms	1052 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
vector<int> adj[MAXN],edge[MAXN];
int res;
bool visited[MAXN];

int dfs(int now){
	int ret=0;
	for(auto nxt : edge[now])ret+=dfs(nxt);
	res+=(ret+1);
	return ret+1;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,k,a;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> k;
		for(int j=1;j<=k;j++){
			cin >> a;
			adj[a].push_back(i);
		}
	}
	int ans=1e9;
	for(int i=1;i<=n;i++){
		memset(visited,0,sizeof(visited));
		for(int i=1;i<=n;i++)edge[i].clear();
		queue<int> Q;
		Q.push(i);
		visited[i]=true;
		while(!Q.empty()){
			int now=Q.front();
			Q.pop();
			for(auto nxt : adj[now]){
				if(!visited[nxt]){
					edge[now].push_back(nxt);
					visited[nxt]=true;
					Q.push(nxt);
				}
			}
		}
		bool cek=true;
		for(int j=1;j<=n;j++){
			if(!visited[j]){
				cek=false;
				break;
			}
		}
		if(!cek)continue;
		res=0;
		dfs(i);
		ans=min(ans,res);
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33