Submission #1091824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091824		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	519 ms	860 KiB

bosses

#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int maxn = 5010, inf = 1e18;

int h[maxn], n, comp, tmp;

vector<int> adj[maxn];
bool mark[maxn];

queue<int> q;

void bfs(int source){
	q.push(source);
	h[source] = 1;
	mark[source] = true;
	while(q.size()){
		comp++;
		int v = q.front();
		q.pop();
		tmp += h[v];
		for(auto u : adj[v]){
			if(!mark[u]){
				h[u] = h[v] + 1;
				mark[u] = true;
				q.push(u);
			}
		}
	}
}

int32_t main(){
	
	ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);
	
	cin >> n;
	for(int i =1 ; i<= n; i++){
		int sz;
		cin >> sz;
		while(sz--){
			int x;
			cin >> x;
			adj[x].push_back(i);
		}
	}
	
	int ans = inf;
	
	for(int i = 1; i <= n ; i++){
		for(int i = 1 ; i<= n; i++){
			mark[i] = 0;
			h[i] = 0;
		}
		
		comp = 0;
		tmp = 0;
		bfs(i);
		if(comp == n){
			ans = min(ans ,tmp);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

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