Submission #531841

#	Time	Username	Problem	Language	Result	Execution time	Memory
531841		devariaota	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	204 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

signed main(){
    cin.tie(0) -> ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    vector<vector<int>> adj(n, vector<int>()), adj2(n, vector<int>());
    // int r = -1;
    for(int i=0;i<n;i++)
    {
        int k;
        cin >> k;
        // if(k == 0) r = i;
        for(int j=0;j<k;j++)
        {
            int x;
            cin >> x; x--;
            adj[x].push_back(i); 
        }
    }
    // if(r == -1)
    // {
    //     int mx = 0;
    //     for(int i=0;i<n;i++)
    //     {
    //         if(adj[i].size() > mx)
    //         {
    //             mx = adj[i].size();
    //             r = i;
    //         }
    //     }
    // }

    int ans = LLONG_MAX;
    for(int r=0;r<n;r++)
    {
        queue<int> q;
        q.push(r);
        int cnt = 1;
        vector<bool> vis(n);
        vis[r] = 1;
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(auto i : adj[u])
            {
                if(!vis[i])
                {
                    vis[i] = 1;
                    q.push(i);
                    cnt++;
                }
            }
        }
        vector<int> sm(n);
        fill(vis.begin(), vis.end(), 0);
        function<int(int)> Dfs = [&](int v){
            int ret = 1;
            for(auto i : adj[v])
            {
                if(!vis[i]){
                    vis[i] = 1;
                    ret += Dfs(i);
                }
            }
            // cout << v << " : " << ret << '\n';
            return sm[v] = ret;
        };
        vis[r] = 1;
        Dfs(r);
        int cur = 0;
        for(int i=0;i<n;i++) cur += sm[i];
        if(cnt == n)
        {
            ans = min(ans, cur);
        }
    }
    cout << ans << '\n';

}

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