Submission #927925

#	Time	Username	Problem	Language	Result	Execution time	Memory
927925		TAhmed33	Bosses (BOI16_bosses)	C++98	100 / 100	844 ms	1116 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int n;
vector <int> adj[5001];
int dp[5001] = {};
int d = 0;
bool vis[5001];
vector <int> newadj[5001];
void calc (int pos) {
	dp[pos] = 1;
	d++;
	for (auto j : newadj[pos]) {
		calc(j);
		dp[pos] += dp[j];
	}
}
signed main () {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		while (x--) {
			int y;
			cin >> y;
			adj[y].push_back(i);
		}
	}
	int ans = 1e9;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			dp[j] = 0;
			vis[j] = 0;
			newadj[j].clear();
		}
		queue <int> cur;
		cur.push(i);
		vis[i] = 1;
		while (!cur.empty()) {
			int l = cur.front();
			cur.pop();
			for (auto j : adj[l]) {
				if (!vis[j]) {
					vis[j] = 1;
					newadj[l].push_back(j);
					cur.push(j);
				}
			}
		}
		d = 0;
		calc(i);
		if (d != n) continue;
		int y = 0;
		for (int j = 1; j <= n; j++) {
			y += dp[j];
		}
		if (ans > y) ans = y;
	}
	cout << ans << '\n';
}

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