Submission #1152778

#TimeUsernameProblemLanguageResultExecution timeMemory
1152778sodbayrBosses (BOI16_bosses)C++20
100 / 100
733 ms1132 KiB
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
	vector<ll> q[5005],lt[5005];
	ll w[5005],sm;
ll dfs(ll v){
	ll r=0;
	for(auto u : lt[v]){
		r+=dfs(u);
	}
	sm=sm+r+1;
	return r+1;
}
int main(){
  	ios::sync_with_stdio(false);
  	cin.tie(0);
	cout.tie(0); 	
  	ll n,k,x,s,sum=INT_MAX;
  	cin>>n;
  	for(ll i=1;i<=n;i++){
  		cin>>k;
  		for(ll j=1;j<=k;j++){
  			cin>>x;
  			q[x].pb(i);
  		}
  	}
  	for(ll i=1;i<=n;i++){
  		for(ll j=1;j<=n;j++){
  			w[j]=0;
  			lt[j].clear();
  		}
  		ll c=1;
  		w[i]=1;
  		queue<ll> g;
  		g.push(i);
  		while(g.size()!=0){
  			ll v=g.front();
  			g.pop();
  			for(auto u : q[v]){
  				if(w[u]) continue;
  				c++;
  				w[u]=1;
  				lt[v].pb(u);
  				g.push(u);
  			}
  		}
  		if(c==n){
  			sm=0;
  			dfs(i);
  			sum=min(sum,sm);
  		}
  	}
  	cout<<sum;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...