Submission #654301

#	Time	Username	Problem	Language	Result	Execution time	Memory
654301		bogdanvladmihai	Bosses (BOI16_bosses)	C++14	100 / 100	753 ms	98704 KiB

bosses

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

int main() {
	int n; cin >> n;
	vector<vector<int>> g(n);
	for (int i = 0; i < n; i++) {
		int cnt; cin >> cnt;
		for (int j = 0; j < cnt; j++) {
			int x; cin >> x;
			x--;
			g[x].push_back(i);
		}
	}
	int answer = INT_MAX;
	vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
	for (int u = 0; u < n; u++) {
		queue<int> q;
		q.push(u);
		dist[u][u] = 1;
		int sum = 0, cnt = 0;
		while ((int)q.size() > 0) {
			int x = q.front();
			sum += dist[u][x];
			cnt++;
			q.pop();
			for (const int &v : g[x]) {
				if (dist[u][v] != INT_MAX) {
					continue;
				}
				dist[u][v] = dist[u][x] + 1;
				q.push(v);
			}
		}
		if (cnt == n) {
			answer = min(answer, sum);
		}
	}
	cout << answer << "\n";
	return 0;
}

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