Submission #697784

#	Time	Username	Problem	Language	Result	Execution time	Memory
697784		TranGiaHuy1508	Bosses (BOI16_bosses)	C++17	100 / 100	629 ms	668 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> depth;
vector<vector<int>> adj;

int total;

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++){
		depth.assign(n, 0);

		total = 1;

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

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

		if (!valid) continue;

		res = min(res, total);
	}

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

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