Submission #30683

#	Time	Username	Problem	Language	Result	Execution time	Memory
30683		noobprogrammer	Bosses (BOI16_bosses)	C++14	100 / 100	666 ms	2352 KiB

bosses

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define ii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<ii>

int n , m , visited[5005] , h[5005] ;
ll dp[5005] , res = 1e18 ;
queue<int> q ;
vi adj[5005] ;

void bfs(int x){
	memset(visited , 0 , sizeof visited) ;
	q.push(x);
	h[x] = 1 ;
	ll sum = 0 ;
	visited[x] = 1 ; 
	int cur ,cnt = 0 ;	
	while(!q.empty()){
		cur = q.front() ;
		q.pop() ;
		cnt++ ;
		sum += (ll)h[cur] ;
		for(int v : adj[cur]){
			if(visited[v]) continue ;
			visited[v] = 1 ; h[v] = h[cur] + 1 ; 
			q.push(v) ; 
		}
	}
	if(cnt == n) res = min(res , sum );
	// printf("%d : %lld %lld\n" ,x , sum , res );
	// for(int i = 1 ; i<=n;i++) printf("%d " , h[i]) ;
		// cout <<endl ;
}

int main(){
	// freopen("in.txt" , "r" , stdin) ;
	scanf("%d" ,&n) ;
	int a ,b ; 
	for(int i=1;i<=n;i++){
		scanf("%d" , &a);
		for(int j=0;j<a;j++){
			scanf("%d" , &b) ;
			adj[b].push_back(i) ; 
		}
	}
	for(int i=1;i<=n;i++) bfs(i) ;
	printf("%lld\n" , res)  ;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" ,&n) ;
                  ^
bosses.cpp:44:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &a);
                   ^
bosses.cpp:46:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , &b) ;
                     ^

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