Submission #1275759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275759		hom84287	Bosses (BOI16_bosses)	C++20	100 / 100	424 ms	704 KiB

bosses

#include<bits/stdc++.h>
using namespace std ; 


const int maxn = 5e3+123 , INF=1e9+7 ; 
vector <int> emp[maxn] ;
int n ; 
bool vis[maxn] ; 
int root(int u){
    int res=1 ; 
    queue <pair<int,int>> que  ;
    fill(vis , vis+n+1 , 0) ;
    que.push({u ,1}) ;   
    vis[u]=1 ; 
    while(!que.empty()){
        int ver=que.front().first ,deep=que.front().second ;
        que.pop() ;  
        for(int i:emp[ver]) if(!vis[i]){
            res+=deep+1 ;
            vis[i]=1 ; 
            que.push({i , deep+1}) ; 
        } 
    }
    for(int i=1 ; i<=n ;i++) if(!vis[i]) return INF ;
    //cout<<u<<' '<<res<<'\n';  
    return res ; 
}
int main(){
    cin>>n ; 
    for(int i=1 ; i<=n ; i++){
        int hom ; cin>>hom ; 
        for(int j=0 ; j<hom ; j++){
            int u ; 
            cin>>u ; 
            emp[u].push_back(i) ; 
        }
    }
    int ans=INF ; 
    for(int i=1 ; i<=n; i++)    ans = min(ans , root(i)) ; 
    cout<<ans<<'\n' ;
}

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