Submission #202354

#	Time	Username	Problem	Language	Result	Execution time	Memory
202354		CaroLinda	Bosses (BOI16_bosses)	C++14	100 / 100	1122 ms	888 KiB

bosses

#include <bits/stdc++.h>

const int MAXN = 5e3 + 10 ;
const int inf = 2e9+10 ;

using namespace std ;

int N , K , my_boss ;
long long ans = inf  , cur_ans ;
int deg[MAXN] , par[MAXN] ;
long long val[MAXN] ;
vector<int> adj[MAXN];
bool vis[MAXN] ;

inline void bfs(int S)
{

	memset(vis, false, sizeof vis ) ;
	for(int i = 1 ; i <= N ; i++ ) val[i] = 0 ;

	queue<int> fila ;
	vector<int> ordem ;

	fila.push(S) ;
	par[S] = -1 ;
	vis[S] = true ;
	ordem.push_back(S) ;

	while(!fila.empty() ) 
	{

		int curr = fila.front() ;
		
		fila.pop() ;

		for(int viz : adj[curr] ) 
		{
			if( vis[viz] ) continue ;

			vis[viz] = true ;
			fila.push(viz) ;
			par[viz] = curr ;

			ordem.push_back( viz ) ;
		}

	}

	for(int i = 1 ; i <= N ; i++ )
		if(!vis[i]) return ;

	reverse(ordem.begin() ,ordem.end() ) ;

	for(int i : ordem )
	{
		val[i] += 1LL ;
		if( par[i] != -1 )
			val[ par[i] ] += val[i] ;
	}

	cur_ans = 0LL ;

	for(int i = 1 ; i <= N ; i++ )
		cur_ans += val[i] ;

	ans = min(ans,cur_ans ) ;
}

int main()
{

	scanf("%d", &N ) ;
	for(int i = 1 ; i <= N ; i++ )
	{
		scanf("%d", &K ) ;
		for(int j = 0 ; j < K ; j++ )
		{
			scanf("%d", &my_boss ) ;
			adj[ my_boss ].push_back( i ) ;
		}
	}

	for(int i = 1 ; i <= N ; i++ )
		bfs(i) ;

	printf("%lld\n" , ans ) ;

}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N ) ;
  ~~~~~^~~~~~~~~~~
bosses.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &K ) ;
   ~~~~~^~~~~~~~~~~
bosses.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &my_boss ) ;
    ~~~~~^~~~~~~~~~~~~~~~~

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