Submission #531316

#	Time	Username	Problem	Language	Result	Execution time	Memory
531316		bonk	Bosses (BOI16_bosses)	C++14	100 / 100	706 ms	648 KiB

bosses

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5002;
vector<int>v[N];
int n;

ll ans = 1e18;

void bfs(int s){
    vector<bool>vis(N, 0);
    queue<pair<int, int>>q;
    vis[s] = true;
    q.emplace(s, 1);

    int cnt = 1;
    ll total = 0;

    while(!q.empty()){
        auto now = q.front(); q.pop();

        total += now.second;

        for(auto x: v[now.first]){
            if(!vis[x]){
                cnt++;
                vis[x] = true;
                q.emplace(x, now.second + 1);
            }
        }
    }

    if(cnt == n) ans = min(ans, total);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    for(int i = 1; i <= n; i++){
        int k; cin >> k;
        while(k--){
            int x; cin >> x;
            v[x].push_back(i);
        }
    }
    
    for(int i = 1; i <= n; i++)
        bfs(i);

    cout << ans << endl;

    return 0;
}

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