Submission #220471

#	Time	Username	Problem	Language	Result	Execution time	Memory
220471		Calico	Bosses (BOI16_bosses)	C++17	67 / 100	1585 ms	1064 KiB

bosses

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

int n, ans = 1000000000;
vector<int> adj[5001];
vector<int> adj_tr[5001];
vector<int> dp(5001);

void dfs(int now) {
	int s = 0;
	for (int u: adj_tr[now]) {
		dfs(u);
		s += dp[u];
	}
	dp[now] = s+1;
}

int bfs(int fi) {
	vector<int> dist(n+1, 10000000), prv(n+1);
	queue<int> q;
	q.push(fi); dist[fi] = 1;

	while (q.size()) {
		int now = q.front(); q.pop();

		for (int u: adj[now]) {
			if (dist[u] > dist[now] + 1) {
				dist[u] = dist[now] + 1;
				q.push(u); prv[u] = now;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		adj_tr[i].clear(); dp[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		if (i != fi) {
			if (prv[i] == 0) return ans;
			adj_tr[prv[i]].push_back(i);
		}
	}

	dfs(fi);
	int rs = 0;
	//cout << fi << ": ";
	for (int i = 1; i <= n; i++) {
		rs += dp[i];
		//cout << dp[i] << ' ';
	}
	//cout << '\n';
	return rs;
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int k; cin >> k;
		while (k--) {
			int x; cin >> x;
			adj[x].push_back(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = min(ans, bfs(i));
	}
	cout << ans << '\n';

	return 0;
}

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