Submission #1129765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129765		Nonoze	Bosses (BOI16_bosses)	C++20	0 / 100	0 ms	328 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)

void solve();

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}


int n;
vector<set<int>> adjbase, adj;

pair<int, int> dfs(int x) {
	int ans=0, sm=1;
	for (auto v: adj[x]) {
		auto [ansi, smi] = dfs(v);
		ans+=ansi, sm+=smi;
	}
	ans+=sm;
	return {ans, sm};
}

void solve() {
	cin >> n;
	adjbase.resize(n), adj.resize(n);
	vector<int> cnt(n);
	for (int i=0; i<n; i++) {
		int k; cin >> k;
		for (int j=0; j<k; j++) {
			int x; cin >> x; x--;
			adjbase[x].insert(i);
		}
	}
	int ans=n*n;
	for (int t=0; t<n; t++) {
		queue<int> q; q.push(t);
		vector<int> dist(n, 0);
		vector<bool> visited(n, 0); visited[t]=1;
		adj.clear(), adj.resize(n);
		while (!q.empty()) {
			int u=q.front(); q.pop();
			for (auto v: adjbase[u]) if (!visited[v]) {
				dist[v]=dist[u]+1, visited[v]=1;
				q.push(v);
				adj[u].insert(v);
			}
		}
		ans = min(ans, dfs(t).fi);
	}
	cout << ans << endl;
}

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