제출 #851045

#제출 시각아이디문제언어결과실행 시간메모리
851045emkowBosses (BOI16_bosses)C++17
100 / 100
465 ms912 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define pb emplace_back
#define ins insert
#define ssize(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pld pair <ld, ld>
#define st first
#define nd second

using namespace std;
using ll = int_fast64_t;
// using lll = __int128_t;
using ld = long double;
const int oo = 1e9 + 7;
const int mod = 1e9 + 7;

void solve(){
    int n; cin >> n;
    vector <vector<int>> pos(n);
    for(int i = 0; i < n; i ++){
        int k; cin >> k;
        while(k --){
            int x; cin >> x;
            -- x;
            pos[x].pb(i);
        }
    }
    auto calc = [&](int x){
        vector <vector<int>> g(n);
        vector <bool> vis(n, 0);
        vector <int> d(n, 0);
        queue <int> q;
        q.emplace(x);
        vis[x] = 1;
        d[x] = 1;
        int cnt = 0, r = 0;
        while(ssize(q)){
            int v = q.front();
            q.pop();
            ++ cnt;
            r += d[v];
            for(auto u: pos[v]){
                if(!vis[u]){
                    vis[u] = 1;
                    d[u] = d[v] + 1;
                    q.emplace(u);
                }
            }
        }
        if(cnt != n) return oo;
        return r;
    };
    int ans = oo;
    for(int i = 0; i < n; i ++){
        ans = min(ans, calc(i));
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; t = 1;
    // cin >> t;
    while(t --) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...