Submission #788574

#	Time	Username	Problem	Language	Result	Execution time	Memory
788574		acatmeowmeow	Bosses (BOI16_bosses)	C++11	100 / 100	434 ms	724 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 5e3;
int n, h[N + 5];
bool vis[N + 5];
vector<int> ls[N + 5];
queue<int> q;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int x;
			cin >> x;
			ls[x].push_back(i);
		}
	}
	int ans = 1e18;
	for (int root = 1; root <= n; root++) {
		int res = 0;
		memset(h, 0, sizeof(h));
		memset(vis, 0, sizeof(vis));
		h[root] = 1, vis[root] = true;
		q.push(root);
		while (q.size()) {
			int u = q.front(); q.pop();
			res += h[u];
			for (auto&v : ls[u]) {
				if (vis[v]) continue;
				vis[v] = true, h[v] = h[u] + 1;
				q.push(v);
			}
		}
		bool valid = 1;
		for (int i = 1; i <= n; i++) valid &= vis[i];
		if (valid) ans = min(ans, res);
	}
	cout << ans << '\n';
	return 0;
}

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