Submission #139833

#	Time	Username	Problem	Language	Result	Execution time	Memory
139833		Saboon	Bosses (BOI16_bosses)	C++14	100 / 100	879 ms	888 KiB

bosses

#include <bits/stdc++.h>
 
using namespace std; 
 
typedef long long ll;
 
const int maxn = 5000 + 10;
 
vector<int> g[maxn];
int h[maxn];
 
int Q[maxn];
void bfs(int src){
	int head = 0, tail = 0;
	Q[head ++] = src;
	memset(h, -1, sizeof h);
	h[src] = 0;
	while (tail < head){
		int v = Q[tail ++];
		for (auto u : g[v]){
			if (h[u] == -1){
				h[u] = h[v] + 1;
				Q[head ++] = u;
			}
		}
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int v = 1; v <= n; v++){
		int k;
		cin >> k;
		while (k --){
			int u;
			cin >> u;
			g[u].push_back(v);
		}
	}
	int answer = (n + 1) * n;
	for (int v = 1; v <= n; v++){
		bfs(v);
		int now = 0;
		for (int u = 1; u <= n; u++){
			if (h[u] == -1)
				now = (n + 1) * n;
			else
				now += h[u];
		}
		answer = min(answer, now);
	}
	cout << n + answer << endl;
} 

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