Submission #967898

#	Time	Username	Problem	Language	Result	Execution time	Memory
967898		PM1	Bosses (BOI16_bosses)	C++17	100 / 100	421 ms	732 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
const int mxn=5e3+5;
int n,ans=1e9,mark[mxn];
vector<int>v[mxn];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int k;
		cin>>k;
		while(k--){
			int x;
			cin>>x;
			v[x].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		memset(mark,0,sizeof mark);
		int res=0;
		queue<int>q;
		mark[i]=1;
		q.push(i);
		while(!q.empty()){
			int x=q.front();
			q.pop();
			res+=mark[x];
			for(auto j:v[x]){
				if(!mark[j]){
					mark[j]=mark[x]+1;
					q.push(j);
				}
			}
		}
		int cnt=1;
		for(int j=1;j<=n;j++){
			if(mark[j]==0)
				cnt=0;
		}
		if(!cnt)
			continue;
		ans=min(res,ans);
	}
	cout<<ans;
	return 0;
}

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