Submission #978205

#	Time	Username	Problem	Language	Result	Execution time	Memory
978205		Amaarsaa	Bosses (BOI16_bosses)	C++14	100 / 100	863 ms	1148 KiB

bosses

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
vector < ll > adj[5002], ad[5003];
ll n;
ll C[5003];
void Dfs(ll x) {
	for ( ll X : ad[x]) {
		Dfs(X);
		C[x] += C[X];
	}
	
}
ll Go(ll x) {
	ll i, node;
	queue < ll > q;
	ll D[5003], cnt = 1;
	for (i = 1; i <= n; i ++) D[i] = -1, C[i] = 1, ad[i].clear();
	q.push(x);
	D[x] = 0;
	while(!q.empty()) {
		node= q.front();
		q.pop();
		for ( ll child : adj[node] ) {
			if ( D[child] == -1) {
				q.push(child);
				ad[node].push_back(child);
				cnt ++;
				D[child] = 1;
			}
		}
	}
	if ( cnt != n) return -1;
	Dfs(x);
	ll s = 0;
	for ( i = 1; i <= n; i ++) s += C[i];
	return s;
}

int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll i, j, x, m, s, ans;

	cin >> n;
	
	for (i = 1; i <= n; i ++) {
		cin >> m;
		for (j = 1; j <= m; j ++) {
			cin >> x;
			adj[x].push_back(i);	
		}
	}
	ans = LONG_LONG_MAX;
	for (i = 1; i <= n; i ++) {
		s = Go(i);
		if ( s != -1) ans= min(ans, s);
	}
	cout << ans << endl;
}

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