Submission #349312

#	Time	Username	Problem	Language	Result	Execution time	Memory
349312		S2speed	Bosses (BOI16_bosses)	C++17	67 / 100	1578 ms	4956 KiB

bosses

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

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define gcd __gcd 
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<ll , pll> plll;
typedef pair<int , pii> piii;

const ll MAXN = 5e3 + 20 , md = 1e9 + 7;
// check problem statement

vector<int> adj[MAXN] , bfs;
int dis[MAXN];

int main(){ // check MAXN
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int n , ans = 1e8;
	cin>>n;
	for(int i = 0 ; i < n ; i++){
		ll k;
		cin>>k;
		for(int j = 0 ; j < k ; j++){
			ll v;
			cin>>v; v--;
			adj[v].push_back(i);
		}
	}
	for(int i = 0 ; i < n ; i++){
		memset(dis , 63 , sizeof(dis));
		dis[i] = 1;
		int x = 0 , h = 0;
		bfs.push_back(i);
		while(x < bfs.size()){
			int v = bfs[x];
			for(auto u : adj[v]){
				if(dis[u] > dis[v] + 1){
					dis[u] = dis[v] + 1;
					bfs.push_back(u);
				}
			}
			x++;
		}
		for(int j = 0 ; j < n ; j++){
			if(dis[j] > n){
				h = 1e8;
				break;
			}
			h += dis[j];
		}
		ans = min(ans , h);
	}
	cout<<ans<<'\n';
	return 0;
}

/*

*/

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   while(x < bfs.size()){
      |         ~~^~~~~~~~~~~~

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