Submission #258664

#	Time	Username	Problem	Language	Result	Execution time	Memory
258664		vioalbert	Bosses (BOI16_bosses)	C++14	100 / 100	735 ms	760 KiB

bosses

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

const int N = 5e3+5, INF = 1e9;
int n;
vector<int> adj[N];

void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int c; cin >> c;
		for(int j = 0; j < c; j++) {
			int v; cin >> v;
			adj[v].push_back(i);
		}
	}
}

int bfs(int st) {
	int cur = 0;
	bool vis[n+1] = {0};
	queue<pair<int, int>> q;
	q.push({st, 1});

	// cerr << "---" << st << '\n';
	while(!q.empty()) {
		int u = q.front().first, h = q.front().second; q.pop();
		if(!vis[u]) {
			// cerr << u << ' ' << h << '\n';
			vis[u] = 1;
			cur += h;
			for(int v : adj[u]) if(!vis[v]) {
				q.push({v, h+1});
			}
		}
	}

	for(int i = 1; i <= n; i++) if(!vis[i]) {
		return INF;
	}
	return cur;
}

void solve() {
	int ans = INF;
	for(int i = 1; i <= n; i++) {
		ans = min(ans, bfs(i));
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}

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