Submission #698050

#	Time	Username	Problem	Language	Result	Execution time	Memory
698050		acceptify	Bosses (BOI16_bosses)	C++17	100 / 100	1280 ms	980 KiB

bosses

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

const int mxn = 5005;

int n, k, x, dis[mxn], sal[mxn], sum, ans = 2e9;
vector<int> adj[mxn], adj2[mxn];
queue<int> q;

void bfs(int st) {
	q.push(st);
	dis[st] = 0;
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		for (int i : adj[p]) {
			if (dis[i] != -1) continue;
			q.push(i);
			dis[i] = dis[p] + 1;
			adj2[p].push_back(i);
		}
	}
}

void dfs(int x) {
	sal[x] = 1;
	for (int i : adj2[x]) {
		dfs(i);
		sal[x] += sal[i];
	}
	sum += sal[x];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> k;
		while (k--) {
			cin >> x;
			adj[x].push_back(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dis[j] = -1;
			adj2[j].clear();
		}
		bfs(i);
		for (int j = 1; j <= n; j++) {
			if (dis[j] == -1) goto end;
		}
		sum = 0;
		dfs(i);
		ans = min(ans, sum);
		end:;
	}
	cout << ans << "\n";
}

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