Submission #230971

#	Time	Username	Problem	Language	Result	Execution time	Memory
230971		islingr	Bosses (BOI16_bosses)	C++14	100 / 100	1455 ms	1144 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)

#define eb(x...) emplace_back(x)

template<class T> bool ckmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, 1 : 0; }

constexpr int N = 10 << 9, inf = 1e9;
int n, ans[N];
vector<int> g[N], gt[N];

void dfs(int u, int p) {
	trav(v, gt[u]) {
		if (v == p) continue;
		dfs(v, u);
		ans[u] += ans[v];
	}
}

int solve(int s) {
	rep(u, 0, n) gt[u].clear();
	vector<bool> vis(n);
	queue<int> q; q.push(s);
	vis[s] = true;

	while (!q.empty()) {
		int u = q.front(); q.pop();
		trav(v, g[u]) {
			if (vis[v]) continue;
			gt[u].eb(v);
			q.push(v);
			vis[v] = true;
		}
	}
	rep(u, 0, n) if (!vis[u]) return inf;
	rep(u, 0, n) ans[u] = 1;
	dfs(s, s);
	int ret = 0;
	rep(u, 0, n) ret += ans[u];
	return ret;
}

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

	cin >> n;
	rep(u, 0, n) {
		int k; cin >> k;
		rep(i, 0, k) {
			int v; cin >> v; --v;
			g[v].eb(u);
		}
	}

	int ans = inf;
	rep(u, 0, n) ckmin(ans, solve(u));
	cout << ans;
}

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