Submission #1092513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092513		stdfloat	Bosses (BOI16_bosses)	C++17	22 / 100	1580 ms	348 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

bool tr;

int n, mn = INT_MAX, Sm;

vector<bool> vis;

vector<vector<int>> v, E;

int dfs(int x) {
	int sm = 1;
	vis[x] = true;
	for (auto i : E[x]) {
		if (tr || vis[i]) return tr = true, 0;
		sm += dfs(i);
	}

	Sm += sm;

	return sm;
}

void f(int x, int rt) {
	if (x == rt) f(x + 1, rt);

	if (x == n) {
		Sm = 0;
		tr = false;
		vis.assign(n, false);
		
		dfs(rt);

		if (!tr && !count(vis.begin(), vis.end(), false)) mn = min(mn, Sm);

		return;
	}

	for (auto i : v[x]) {
		E[i].push_back(x);
		
		f(x + 1, rt);

		E[i].pop_back();
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;

	v.assign(n, {});
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		while (k--) {
			int x;
			cin >> x; x--;

			v[i].push_back(x);
		}
	}

	E.assign(n, {});
	for (int i = 0; i < n; i++) {
		f(0, i);
	}

	cout << mn;
}

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