Submission #1278720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278720		IBory	Bosses (BOI16_bosses)	C++20	100 / 100	363 ms	848 KiB

bosses

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAX = 5005;
vector<int> G[MAX];
int N, S[MAX];

ll BFS(int s) {
	S[s] = 1;
	queue<int> Q;
	Q.push(s);
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();
		for (int& next : G[cur]) {
			if (S[next] <= S[cur] + 1) continue;
			S[next] = S[cur] + 1;
			Q.push(next);
		}
	}
	ll ret = 0;
	for (int i = 1; i <= N; ++i) ret += S[i];
	return ret;
}

int main() {
	ll ans = 1e18;
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		int n;
		cin >> n;
		for (int j = 0; j < n; ++j) {
			int p;
			cin >> p;
			G[p].push_back(i);
		}
	}
	for (int i = 1; i <= N; ++i) {
		memset(S, 0x3f, sizeof(S));
		ans = min(ans, BFS(i));
	}
	cout << ans;
	return 0;
}

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