Submission #292192

#	Time	Username	Problem	Language	Result	Execution time	Memory
292192		fadi57	Bosses (BOI16_bosses)	C++14	100 / 100	1085 ms	24568 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 ll n,m,k;
 const int mx=1000000;

const int MOD=1000000007;

//fast exponentiation
int visited[100000];


vector<int>edges[mx];
ll co=0;
ll bfs(int s){
    
    queue<pair<int,int>>q;
    q.push({1,s}); 
    ll sum=0;
    while(!q.empty()){
        pair<int,int>me=q.front();
        q.pop();
        int node=me.second;
        sum+=me.first;
        co++;
        visited[node]=1;
        
        for(int i=0;i<edges[node].size();i++){
            if(!visited[edges[node][i]]){
                q.push({me.first+1,edges[node][i]});
                 visited[edges[node][i]]=1;
            }
            
        }
        
    }if(co==n){return sum;}else{return 1e9;}
    
    
    
    
    
    
    
    
    
}
int main() {
    /*freopen("poetry.in" , "r" , stdin) ;
    freopen("poetry.out" , "w" , stdout) ;
    */
cin>>n;
for(int i=1;i<=n;i++){
    int k;cin>>k;
    for(int j=0;j<k;j++){
        ll y;
            cin>>y; 
            edges[y].push_back(i);
            
    }

}

ll ans=1e9;
for(int i=1;i<=n;i++){
    memset(visited,0,sizeof(visited));
    co=0;  
    ll an=bfs(i);
    if(co==n){ans=min(ans,an);}
  
   // cout<<co<<endl;
    

}
cout<<ans;

}

Compilation message (stderr)

bosses.cpp: In function 'll bfs(int)':
bosses.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i=0;i<edges[node].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~~

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