Submission #218600

#	Time	Username	Problem	Language	Result	Execution time	Memory
218600		KCSC	Bosses (BOI16_bosses)	C++14	100 / 100	797 ms	760 KiB

bosses

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

const int DIM = 5005;

vector<int> edg[DIM];
int mrk[DIM];

int main(void) {
#ifdef HOME
	freopen("bosses.in", "r", stdin);
	freopen("bosses.out", "w", stdout);
#endif
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int k; cin >> k;
		for (int j = 1; j <= k; ++j) {
			int x; cin >> x;
			edg[x].push_back(i);
		}
	}
	int ans = (1 << 30);
	for (int s = 1; s <= n; ++s) {
		for (int i = 1; i <= n; ++i)
			mrk[i] = 0;
		mrk[s] = 1;
		deque<int> que(1, s);
		int cst = 0;
		for (; que.size(); que.pop_front()) {
			int x = que.front();
			cst += mrk[x];
			for (int y : edg[x]) if (!mrk[y]) {
				mrk[y] = mrk[x] + 1;
				que.push_back(y);
			}
		}
		for (int i = 1; i <= n; ++i)
			if (!mrk[i])
				cst = (1 << 30);
		ans = min(ans, cst);
	}
	cout << ans << endl;
	return 0;
}

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