Submission #108512

#	Time	Username	Problem	Language	Result	Execution time	Memory
108512		maruii	Bosses (BOI16_bosses)	C++14	100 / 100	821 ms	836 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

vector<int> edge[5001];
bool vis[5001];

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin>>N;
	for(int i=1; i<=N; ++i){
		int k; cin>>k;
		while(k--){
			int x; cin>>x;
			edge[x].push_back(i);
		}
	}
	int ans = 1e9;
	for(int i=1; i<=N; ++i){
		queue<pii> q;
		int sum = 0, cnt = 0;
		memset(vis+1, 0, N);
		q.emplace(i, 1); vis[i] = 1;
		while(q.size()){
			auto x = q.front(); q.pop();
			sum += x.ss;
			++cnt;
			for(auto i: edge[x.ff]){
				if(vis[i]) continue;
				vis[i] = 1;
				q.emplace(i, x.ss+1);
			}
		}
		if(cnt == N) ans = min(ans, sum);
	}
	cout<<ans;
	return 0;
}

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