Submission #951875

#	Time	Username	Problem	Language	Result	Execution time	Memory
951875		MohamedAhmed04	Bosses (BOI16_bosses)	C++14	100 / 100	424 ms	848 KiB

bosses

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5000 + 10 ;

int n ;
vector< vector<int> >adj(MAX) ;

int dep[MAX] , vis[MAX] ;

int solve(int boss)
{
    for(int i = 1 ; i <= n ; ++i)
        vis[i] = 0 ;
    int cnt = 0 , sum = 0 ;
    queue<int>q ;
    q.push(boss) ;
    dep[boss] = 1 , vis[boss] = 1 ;
    while(!q.empty())
    {
        int node = q.front() ;
        q.pop() ;
        cnt++ , sum += dep[node] ;
        for(auto &child : adj[node])
        {
            if(!vis[child])
            {
                vis[child] = 1 ;
                dep[child] = dep[node] + 1 ;
                q.push(child) ;
            }
        }
    }
    if(cnt != n)
        sum = 2e9 ;
    return sum ;
}

int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cin>>n ;
    for(int i = 1 ; i <= n ; ++i)
    {
        int sz ;
        cin>>sz ;
        while(sz--)
        {
            int node ;
            cin>>node ;
            adj[node].push_back(i) ;
        }
    }
    int ans = 1e9 ;
    for(int i = 1 ; i <= n ; ++i)
        ans = min(ans , solve(i)) ;
    return cout<<ans<<"\n" , 0 ;
}

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