Submission #1108462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108462		nasir_bashirov	Bosses (BOI16_bosses)	C++11	100 / 100	466 ms	772 KiB

bosses

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define int long long

const int sz = 5e3 + 5;
vi g[sz];
int n, m, x, res = 1e18;

void fmain(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> m;
        for(int j = 1; j <= m; j++){
            cin >> x;
            g[x].push_back(i);
        }
    }
    for(int root = 1; root <= n; root++){
        int ans = 0;
        queue<pii> q;
        vi used(n + 5, 0);
        q.push({root, 1});
        int cnt = 0;
        while(!q.empty()){
            int cur = q.front().first, w = q.front().second;
            q.pop();
            if(used[cur])   continue;
            cnt++;
            ans += w;
            used[cur] = 1;
            for(int i : g[cur]){
                if(used[i]) continue;
                q.push({i, w + 1});
            }
        }
        if(cnt == n)    res = min(res, ans);
    }
    cout << res;
}
 
signed main(){
    int tmr = 1;
    // cin >> tmr;
    while(tmr--){
        fmain();
    }
}

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