Submission #865931

#	Time	Username	Problem	Language	Result	Execution time	Memory
865931		maks007	Bosses (BOI16_bosses)	C++14	0 / 100	62 ms	348 KiB

bosses

#include "bits/stdc++.h"

using namespace std;

signed main () {
	int n, ans = 1e9;
	cin >> n;
	vector <pair <int,int>> edge;
	for(int i = 0; i < n; i ++) {
		int sz;
		cin >> sz;
		while(sz --) {
			int v;
			cin >> v;
			edge.push_back({v-1, i});
		}
	}
	for(int mask = 0; mask < (1 << edge.size()); mask ++) {
		if(__builtin_popcount(mask) != n-1) continue;
		vector <int> g[n], dp(n), stock(n, 0), used(n);
		int f = 0;

		function <void(int)> check=[&](int v) {
			used[v] = 1;
			for(auto u : g[v]) {
				if(!used[u]) check(u);
				else if(used[u] == 1) f = 1;
			}
			used[v] = 2;
		};

		function <void(int,int)> dfs=[&](int v, int p) {
			for(auto u : g[v]) {
				if(u == p) continue;
				dfs(u, v);
				dp[v] += dp[u];
			}
		};
		for(int i = 0; i < edge.size(); i ++) {
			if(mask & (1 << i)) {
				dp[edge[i].first] = 1;
				dp[edge[i].second] = 1;
				stock[edge[i].second] ++;
				g[edge[i].first].push_back(edge[i].second);
			}
		}
		for(int i = 0; i < n; i ++) {
			if(!used[i]) check(i);
		}
		if(f) continue;
		int root = -1;
		for(int i= 0; i < n; i ++) {
			if(stock[i] == 0 && dp[i] == 1) {
				if(root == -1) root = i;
				else {
					goto end;
				}
			}
		}
		if(root == -1) continue;
		dfs(root, -1);
		ans = min(accumulate(dp.begin(), dp.end(), 0), ans);
		end:;
	}
	cout << ans + 1;
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i = 0; i < edge.size(); i ++) {
      |                  ~~^~~~~~~~~~~~~

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