Submission #24888

#	Time	Username	Problem	Language	Result	Execution time	Memory
24888		RezwanArefin01	Bosses (BOI16_bosses)	C++14	100 / 100	696 ms	2324 KiB

bosses

//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 5555; 
vector<int> adj[maxn];
int vis[maxn], dist[maxn], n; 

ll bfs(int u) {
	queue<int> Q;
	memset(vis, 0, sizeof vis); 
	memset(dist, 0, sizeof dist); 
	vis[u] = 1;
	dist[u] = 1; 
	Q.push(u);
	while(!Q.empty()) {
		int u = Q.front(); Q.pop(); 
		for(int v : adj[u]) if(!vis[v]) {
			Q.push(v); 
			dist[v] = dist[u] + 1; 
			vis[v] = 1;
		}
	} ll sum = 0;
	for(int i=1; i<=n; i++) {
		if(!vis[i]) return 1e9; 	
		sum += dist[i];
	} return sum; 
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	cin>>n; 
	for(int i=1; i<=n; i++) {
		int k; cin>>k ;
		while(k--) {
			int p; cin>>p;
			adj[p].push_back(i); 
		}
	} 
	ll Min = 1e9;
	for(int i=1; i<=n; i++) 
		Min = min(Min, bfs(i));  
	cout<<Min<<endl;
} 

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