Submission #533185

#	Time	Username	Problem	Language	Result	Execution time	Memory
533185		gilbirb	Bosses (BOI16_bosses)	C++14	100 / 100	622 ms	648 KiB

bosses

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
typedef long long ll;
using namespace std;

ll n, ans = 1e9;
vector<ll>adj[5005];
ll p[5005];

void bfs(ll s){
	memset(p, 0, sizeof(p));
	p[s] = 1;
	queue<ll>q;
	q.push(s);
	while(!q.empty()){
		ll cur = q.front();
		q.pop();
		for(int x : adj[cur]){
			if(!p[x]){
				p[x] = p[cur]+1;
				q.push(x);
			}
		}
	}
	ll total = 0;
	for(int i = 1; i <= n; i++){
		if(!p[i]) return;
		total += p[i];
	}
	ans = min(ans, total);
	return;
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int m;
		cin >> m;
		for(int j = 1; j <= m; j++){
			ll x; cin >> x;
			adj[x].pb(i);
		}
	}
	for(int i = 1; i <= n; i++){
		bfs(i);
	}
	cout << ans << endl;
	
}

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