Submission #697782

#	Time	Username	Problem	Language	Result	Execution time	Memory
697782		TranGiaHuy1508	Bosses (BOI16_bosses)	C++17	67 / 100	1582 ms	928 KiB

bosses

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

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

int n;
vector<int> vst;
vector<vector<int>> adj, structure;

int total;

int dfs(int x, int p = -1){
	int sum = 0;
	for (auto k: structure[x]){
		if (k == p) continue;
		sum += dfs(k, x);
	}
	total += sum + 1;
	return sum + 1;
}

void main_program(){
	cin >> n;

	adj.resize(n);

	for (int i = 0; i < n; i++){
		int sz; cin >> sz;
		for (int j = 0; j < sz; j++){
			int x; cin >> x; x--;
			adj[x].push_back(i);
		}
	}

	int res = 1e9;

	for (int root = 0; root < n; root++){
		vst.assign(n, 0);
		structure.clear(); structure.resize(n);

		queue<int> q; q.push(root); vst[root] = 1;
		while (!q.empty()){
			int x = q.front(); q.pop();
			for (auto k: adj[x]){
				if (!vst[k]){
					vst[k] = 1;
					structure[x].push_back(k);
					q.push(k);
				}
			}
		}

		bool valid = true;
		for (int i = 0; i < n; i++){
			if (!vst[i]){
				valid = false;
				break;
			}
		}

		if (!valid) continue;

		total = 0; dfs(root);
		res = min(res, total);
	}

	cout << res << "\n";
}

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