Submission #813245

#	Time	Username	Problem	Language	Result	Execution time	Memory
813245		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	801 ms	960 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
const int NM = 5000;
const int INF = 1e9+7;
vector<int> g[NM+5];
bool vis[NM+5];
vector<int> g2[NM+5];
int val[NM+5];
void bfs(int u){
	queue<int> q;
	q.push(u);
	vis[u] = 1;
	while(!q.empty()){
		u = q.front(); q.pop();
		g2[u].clear();
		for (int& v : g[u]){
			if (vis[v]) continue;
			g2[u].push_back(v);
			vis[v] = 1;
			q.push(v);
		}
	}
}
void dfs(int u){
	val[u] = 1;
	for (int& v : g2[u]){
		dfs(v);
		val[u] += val[v];
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){
		int k;
		cin >> k;
		for (int j = 0; j < k; j++){
			int x; cin >> x;
			g[x].push_back(i);
		}
	}
	int res = INF;
	for (int i = 1; i <= n; i++){
		memset(vis, 0, sizeof vis);
		bfs(i);
		bool ok = true;
		for (int j = 1; j <= n; j++){
			if (vis[j] == false){
				ok = false;
				break;
			}
		}
		if (ok){
			dfs(i);
			int sum = 0;
			for (int j = 1; j <= n;j++){
				sum += val[j];
			}
			res = min(res, sum);
		}
	}
	cout << res << endl;
	return 0;
}

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