Submission #851042

#	Time	Username	Problem	Language	Result	Execution time	Memory
851042		emkow	Bosses (BOI16_bosses)	C++17	67 / 100	1554 ms	1468 KiB

bosses

#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);
        queue <int> q;
        q.emplace(x);
        vis[x] = 1;
        int cnt = 0;
        while(ssize(q)){
            int v = q.front();
            q.pop();
            ++ cnt;
            for(auto u: pos[v]){
                if(!vis[u]){
                    vis[u] = 1;
                    g[v].pb(u);
                    g[u].pb(v);
                    q.emplace(u);
                }
            }
        }
        if(cnt != n) return oo;
        vector <int> dp(n, 0);
        function<void(int, int)> dfs = [&](int v, int p){
            for(auto u: g[v]){
                if(u == p) continue;
                dfs(u, v);
                dp[v] += dp[u];
            }
            dp[v] ++;
        };
        dfs(x, -1);
        return accumulate(all(dp), 0);
    };
    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;
}

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