Submission #350854

#	Time	Username	Problem	Language	Result	Execution time	Memory
350854		Parsa_PG	Bosses (BOI16_bosses)	C++14	100 / 100	911 ms	896 KiB

bosses

/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
 
using namespace std;
 
const int maxn = 5e3 + 10, Maxn = 1e5 + 10, SQ = 360 , lg = 22 ; 
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;

vector<int>adj1[maxn] , adj[maxn];
int h[maxn] , val[maxn] , n;
bool vis[maxn];

int bfs(int s){
	for(int i =  0 ;i  < n; i++){
		h[i] = 0;
		vis[i] =0;
		adj[i].clear();
		val[i] = 0;
	}
	queue<int>q;
	q.push(s);
	vis[s] = 1;
	h[s] = 1;
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(auto u : adj1[v]){
			if(!vis[u]){
				q.push(u);
				vis[u] = 1;
				h[u] = h[v] + 1;
			}
		}
	}
	int res = 0;
	for(int i = 0 ; i < n ; i++){
		if(h[i] == 0)
			return inf;
		res += h[i];
	}
	return res;
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0 ; i < n ; i ++){
		int k;
		cin >> k;
		for(int j = 0 ; j < k ; j++){
			int u;
			cin >> u;
			u--;
			adj1[u].pb(i);
		}
	}
	int ans = inf;
	for(int i = 0 ; i < n ; i++){
		ans = min(ans , bfs(i));
	}
	cout << ans << endl;
	return 0;
}

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