Submission #113328

#	Time	Username	Problem	Language	Result	Execution time	Memory
113328		ckodser	Bosses (BOI16_bosses)	C++14	100 / 100	556 ms	764 KiB

bosses

#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=5500;
const ll inf=1e9+900;


vector<ll> ger[maxn];
ll h[maxn];
bool vis[maxn];

ll find_min(ll a,ll n){
    memset(vis,0,sizeof vis);
    queue<ll> qu;
    h[a]=1;
    vis[a]=1;
    ll cnt=1;
    ll ans=1;
    qu.push(a);
    while(qu.size()){
	ll v=qu.front();
	qu.pop();
	for(auto u:ger[v]){
	    if(!vis[u]){
		vis[u]=1;
		qu.push(u);
		h[u]=h[v]+1;
		ans+=h[u];
		cnt++;
	    }
	}
    }
    if(cnt!=n)return inf;
    return ans;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,m;
    cin>>n;
    for(ll i=1;i<=n;i++){
	ll k;
	cin>>k;
	while(k--){
	    ll v;
	    cin>>v;
	    ger[v].pb(i);
	}
    }
    ll ans=inf;
    for(ll i=1;i<=n;i++){
	ans=min(ans,find_min(i,n));
    }
    cout<<ans;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:48:10: warning: unused variable 'm' [-Wunused-variable]
     ll n,m;
          ^

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