oj.uz

Submission #865931

# Submission time Handle Problem Language Result Execution time Memory
865931 2023-10-25T03:56:03 Z maks007 Bosses (BOI16_bosses) C++14
0 / 100
 62 ms 348 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Incorrect 62 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Incorrect 62 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Incorrect 62 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -