Submission #1066415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066415		boris_7	Bosses (BOI16_bosses)	C++17	100 / 100	533 ms	860 KiB

bosses

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<ll>>gp;
vector<ll>vis;
vector<ll> d;
ll n;
ll ans = LLONG_MAX;

void bfs(ll u){
    queue<ll>q;
    q.push(u);
    vis[u]=1;
    d[u]=1;
    ll cnt = 0,comp=0;
    while(q.size()){
        ll v = q.front();
        q.pop();
        comp++;
        cnt+=d[v];
        for(ll &i:gp[v]){
            if(!vis[i]){
                vis[i]=1;
                d[i]=d[v]+1;
                q.push(i);
            }
        }
    }
    if(comp==n){
        ans = min(ans,cnt);
    }
}

void solve(){
    cin>>n;
    gp = vector<vector<ll>>(n);
    for(ll i =0;i<n;i++){
        ll x;
        cin>>x;
        while(x--){
            ll v;
            cin>>v;
            gp[--v].push_back(i);
        }
    }
    for(ll i = 0;i<n;i++){
        vis = vector<ll>(n);
        d = vector<ll>(n);
        bfs(i);
    }
    cout<<ans<<endl;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // ll t;cin>>t;while(t--)
        solve();
}

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