Submission #484664

#	Time	Username	Problem	Language	Result	Execution time	Memory
484664		minhcool	Bosses (BOI16_bosses)	C++17	100 / 100	595 ms	3012 KiB

bosses

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n;

vector<int> Adj[N];

int ans = oo;

int mn_dist[N];

void bfss(int u){
	for(int i = 1; i <= n; i++) mn_dist[i] = oo;
	mn_dist[u] = 0;
	queue<int> bfs;
	bfs.push(u);
	while(!bfs.empty()){
		int u = bfs.front();
		bfs.pop();
		for(auto v : Adj[u]){
			if(mn_dist[v] != oo) continue;
			mn_dist[v] = mn_dist[u] + 1;
			bfs.push(v);
		}
	}
	int tol = 0;
	for(int i = 1; i <= n; i++){
		//cout << u << " " << i << " " << mn_dist[i] << "\n";
		if(mn_dist[i] == oo){
			tol += mn_dist[i];
			break;
		}
		tol += mn_dist[i];
	}
	ans = min(ans, tol);
}

void process(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		while(x--){
			int y;
			cin >> y;
			Adj[y].pb(i);
		}
	}
	for(int i = 1; i <= n; i++) bfss(i);
	cout << ans + n << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

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