Submission #1129770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129770		Nonoze	Bosses (BOI16_bosses)	C++20	67 / 100	1584 ms	1024 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<vector<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].pb(i);
		}
	}
	int ans=n*n;
	for (int t=0; t<n; t++) {
		queue<int> q; q.push(t);
		vector<int> dist(n, n*n); dist[t]=0;
		vector<bool> visited(n, 0);
		adj.clear(), adj.resize(n);
		while (!q.empty()) {
			int u=q.front(); q.pop();
			if (visited[u]) continue;
			visited[u]=1;
			for (auto v: adjbase[u]) {
				if (dist[v]<=dist[u]+1) continue;
				dist[v]=dist[u]+1;
				q.push(v);
				adj[u].pb(v);
			}
		}
		bool ok=1;
		for (int i=0; i<n; i++) {
			if (!visited[i]) ok=0;
		}
		if (!ok) continue;
		cmin(ans, dfs(t).fi);
	}
	cout << ans << endl;
}

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