Submission #698049

#	Time	Username	Problem	Language	Result	Execution time	Memory
698049		acceptify	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	468 KiB

bosses

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

const int mxn = 5005;

int n, k, x, dis[mxn], sal[mxn], boss = -1, 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;
		if (!k) boss = i;
		while (k--) {
			cin >> x;
			adj[x].push_back(i);
		}
	}
	if (boss != -1) {
		for (int j = 1; j <= n; j++) {
			dis[j] = -1;
			adj2[j].clear();
		}
		bfs(boss);
		sum = 0;
		dfs(boss);
		ans = sum;
	} else {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dis[j] = -1;
				adj2[j].clear();
			}
			bfs(i);
			sum = 0;
			dfs(i);
			ans = min(ans, sum);
		}
	}
	cout << ans << "\n";
}

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