Submission #223569

#	Time	Username	Problem	Language	Result	Execution time	Memory
223569		kshitij_sodani	Bosses (BOI16_bosses)	C++17	100 / 100	790 ms	760 KiB

bosses

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
vector<int> adj[5001];
int n;
int bfs(int no){
	int dist[n];
	for(int i=0;i<n;i++){
		dist[i]=-1;
	}
	dist[no]=0;
	queue<int> dd;
	dd.push(no);
	while(dd.size()){
		int x=dd.front();
		dd.pop();
		for(auto jj:adj[x]){
			if(dist[jj]==-1 or dist[jj]>dist[x]+1){
				dist[jj]=dist[x]+1;
				dd.push(jj);
			}
		}
	}

	for(int i=0;i<n;i++){
		if(dist[i]==-1){
			return -1;
		}
	}
	int ans=n;
	for(int i=0;i<n;i++){
		ans+=dist[i];
	}


	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;

	for(int i=0;i<n;i++){
		int k;
		cin>>k;
		int aa;
		for(int j=0;j<k;j++){
			cin>>aa;
			adj[aa-1].pb(i);
		}
	}
	int mi=1000000000;
	for(int i=0;i<n;i++){
		int ma=bfs(i);
		if(ma>-1){
			mi=min(mi,ma);
		}
	}
	cout<<mi<<endl;
	return 0;
}

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