Submission #723479

#	Time	Username	Problem	Language	Result	Execution time	Memory
723479		bane	Bosses (BOI16_bosses)	C++17	100 / 100	1283 ms	1008 KiB

bosses

#include<bits/stdc++.h>
   
using namespace std;
   
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif



int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int>g[n];
    for (int i = 0 ; i < n; i++){
		int k;
		cin >> k;
		while(k--){
			int x;
			cin >> x;
			--x;
			g[x].emplace_back(i);
		}
	}
	int visited[n];
	vector<int>adj[n];
	int ans = (int)1e9;
	for (int i = 0; i < n; i++){
		queue<int>q;
		q.push(i);
		for (int j = 0; j < n; j++){
			visited[j] = 0;
			adj[j].clear();
		}
		int cnt = 0;
		while(!q.empty()){
			int node = q.front();
			q.pop();
			++cnt;
			visited[node] = 1;
			for (auto p : g[node]){
				if(!visited[p]){
					visited[p] = 1;
					q.push(p);
					adj[node].emplace_back(p);
				}
			}
		}
		if (cnt < n)continue;
		function<pair<int,int>(int,int)>dfs = [&](int u, int p){
			int sum = 1;
			int tot = 0;
			for (int& x : adj[u]){
				if (x == p)continue;
				auto m = dfs(x,u);
				sum+=m.first;
				tot+=m.second;
			}
			tot+=sum;
			return make_pair(sum, tot);
		};
		ans = min(ans,dfs(i,-1).second);
	}
	cout<<ans;
    return 0;
}

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