Submission #1303538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303538		ffeyyaae_	Bosses (BOI16_bosses)	C++20	100 / 100	685 ms	1016 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

const int N = 5005;

int n;
vector<int> child[N], adj[N];
bool vis[N];
int sal[N];

void dfs( int u )
{
    sal[u] = 1;
    for( auto v : adj[u] )
    {
        dfs(v);
        sal[u] += sal[v];
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for( int i=1;i<=n;i++ )
    {
        int k;
        cin >> k;
        for( int j=0;j<k;j++ )
        {
            int a;
            cin >> a;
            child[a].push_back(i);
        }
    }
    int mn = 1e9;
    for( int i=1;i<=n;i++ )
    {
        fill( vis+1, vis+n+1, false );
        vis[i] = true;
        queue<int> q;
        q.push(i);
        while( !q.empty() )
        {
            int node = q.front();
            q.pop();
            adj[node].clear();
            for( int cur : child[node] )
            {
                if( vis[cur] ) continue;
                vis[cur] = true;
                adj[node].push_back(cur);
                q.push(cur);
            }
        }
        bool chk = false;
        for( int j=1;j<=n;j++ )
        {
            if( !vis[j] )
            {
                chk = true;
                break;
            }
        }
        if( chk ) continue;
        dfs(i);
        int sum = 0;
        for( int j=1;j<=n;j++ ) sum += sal[j];
        mn = min( mn, sum );
    }
    cout << mn << "\n";
    return 0;
}

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