Submission #1305191

#TimeUsernameProblemLanguageResultExecution timeMemory
1305191metaliusBosses (BOI16_bosses)C++20
100 / 100
800 ms792 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;

int n;

int ans(int root, vii & adj) {
	vector<bool> used(n+1);
	vector<ll> dp(n+1);
	vector<int> par(n+1);
	stack<int> order;
	queue<int> q;
	q.push(root);
	used[root] = true;
	int vis = 0;
	while(!q.empty()) {
		int v = q.front();
		q.pop();
		used[v] = true;
		vis++;
		order.push(v);
		for(auto cld : adj[v]) {
			if(!used[cld]) {
				q.push(cld);
				used[cld] = true;
				par[cld] = v;
			}
		}
	}
	ll res = 0;
	if(vis != n) return INT32_MAX;
	// detect leaves
	while(!order.empty()) {
		int fr = order.top();
		order.pop();
		for(auto cld : adj[fr]) {
			if(par[cld] == fr) {
				dp[fr] += dp[cld];				
			}
		}
		dp[fr]++;
		res += dp[fr];
	}
	return res;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	vii adj(n+1);
	for(int i = 1; i <= n;i++) {
		int k; cin >> k;
		for(int j = 0; j < k; j++) {
			int a; cin >> a;
			adj[a].push_back(i);
		}
	}
	int res = INT32_MAX;
	for(int i = 1; i <= n;i++) {
		res = min(res,ans(i,adj));
	}	
	cout << res;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...