제출 #76875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76875		shoemakerjo	Bosses (BOI16_bosses)	C++14	100 / 100	718 ms	1560 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

#define maxn 5010
int n;


bool vis[maxn];
vector<vector<int>> ch(maxn);
queue<int> q;
int dep[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int v;
	for (int i = 1; i <= n; i++) {
		int ct;
		cin >> ct;
		for (int j = 0; j < ct; j++) {
			cin >> v;
			ch[v].push_back(i);
		}
		
	}
	int ans = n*n;
	for (int i = 1; i <= n; i++) {
		fill(vis, vis+maxn, false);
		q.push(i);
		dep[i] = 1;
		vis[i] = true;
		int cans = 1;
		while (!q.empty()) {
			v = q.front(); q.pop();
			for (int vv : ch[v]) {
				if (!vis[vv]) {
					dep[vv] = dep[v]+1;
					vis[vv] = true;
					cans += dep[vv];
					q.push(vv);
				}
			}
		}
		bool ok = true;
		for (int j = 1; j <= n; j++) {
			if (!vis[j]) {
				ok = false;
				// cout << "missed!" << endl;
			}
		}
		if (ok) ans = min(ans, cans);
	}
	cout << ans << endl;
}

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