제출 #1152778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152778		sodbayr	Bosses (BOI16_bosses)	C++20	100 / 100	733 ms	1132 KiB

bosses

#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;
}

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