Submission #1259182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259182		Jer	Bosses (BOI16_bosses)	C++20	0 / 100	1 ms	580 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

const int MAXN = 5005;
vi con[MAXN];
bool used[MAXN];
vi pos[MAXN];
int n;
int val[MAXN];

void clear() {
	for (int i = 1; i <= n; i++)
		used[i] = false, val[i] = 0, con[i].clear();
}

void make(int curr) {
	used[curr] = true;
	for (auto i : pos[curr])
		if (!used[i])
			con[curr].push_back(i), make(i);
}

int cnt(int curr) {
	int res = 1;
	for (auto i : con[curr])
		res += cnt(i);
	return (val[curr] = res);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;

	int m, c;
	for (int i = 1; i <= n; i++) {
		cin >> m;
		for (int j = 0; j < m; j++)
			cin >> c, pos[c].push_back(i);
	}
	
	int res = INT_MAX;
	for (int i = 1; i <= n; i++) {
		clear(), make(i), cnt(i);

		int sum = 0; bool pos = true;

		for (int j = 1; j <= n; j++) if (val[j] == 0) pos = false;
		if (!pos) continue;

		for (int j = 1; j <= n; j++) sum += val[j];
		res = min(res, sum);
	}

	cout << res << '\n';

	return 0;
}

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