Submission #693829

#	Time	Username	Problem	Language	Result	Execution time	Memory
693829		ajab_01	Bosses (BOI16_bosses)	C++17	100 / 100	1307 ms	884 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
 
const int N = 5e3 + 3;
const long long INF = 1e18;
vector<int> g[N] , vec[N];
deque<int> dq;
bool vis[N];
long long ans = INF;
int level[N] , n;
 
void bfs(int root){
	vis[root] = 1;
	dq.push_back(root);
	level[root] = 1;
	while(!dq.empty()){
		int ver = dq.front();
		dq.pop_front();
		for(int i : vec[ver]){
			if(vis[i]) continue;
			vis[i] = 1;
			g[ver].push_back(i);
			g[i].push_back(ver);
			dq.push_back(i);
			level[i] = level[ver] + 1;
		}
	}
}
 
long long cal(int root){
	bfs(root);
	long long res = 0;
	bool ch = 1;
	for(int i = 1 ; i <= n ; i++){
		g[i].clear();
		res += level[i];
		if(!vis[i])
			ch = 0;
		vis[i] = 0;
	}
	return (ch ? res : INF);
}
 
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		int x;
		cin >> x;
		while(x--){
			int j;
			cin >> j;
			vec[j].push_back(i);
		}
	}
 
	for(int i = 1 ; i <= n ; i++)
		ans = min(ans , cal(i));
 
	cout << ans << '\n';
	return 0;
}

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