Submission #693742

#	Time	Username	Problem	Language	Result	Execution time	Memory
693742		ajab_01	Bosses (BOI16_bosses)	C++17	67 / 100	1592 ms	1016 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 , val[N];
int n;

void bfs(int root){
	vis[root] = 1;
	dq.push_back(root);
	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);
		}
	}
}

void dfs(int ver , int par){
	val[ver] = 1;
	for(int i : g[ver]){
		if(i == par) continue;
		dfs(i , ver);
		val[ver] += val[i];
	}
}

long long cal(int root){
	bfs(root);
	dfs(root , 0);
	long long res = 0;
	bool ch = 1;
	for(int i = 1 ; i <= n ; i++){
		g[i].clear();
		res += val[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: 0 / 33