Submission #865939

#	Time	Username	Problem	Language	Result	Execution time	Memory
865939		maks007	Bosses (BOI16_bosses)	C++14	100 / 100	1202 ms	1664 KiB

bosses

#include "bits/stdc++.h"

using namespace std;

#define int long long

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, ans = LLONG_MAX;
	cin >> n;
	vector <int> g[n], g2[n];
	for(int i = 0; i < n; i ++) {
		int sz;
		cin >> sz;
		while(sz --) {
			int v;
			cin >> v;
			g[v-1].push_back(i);
		}
	}
	queue <int> q;
	for(int i = 0; i < n; i ++) {
		vector <int> dist(n, LLONG_MAX);
		dist[i] = 0;
		q.push(i);
		vector <pair <int,int>> temp;
		while(!q.empty()) {
			int v = q.front();
			q.pop();
			for(auto u : g[v]) {
				if(dist[u] == LLONG_MAX) {
					temp.push_back({v, u});
					dist[u] = dist[v] + 1;
					q.push(u);
				}
			}
		}
		if(count(dist.begin(), dist.end(), LLONG_MAX)) continue;
		vector <int> dp(n, 1);
		function <void(int,int)> dfs=[&](int v, int p) {
			for(auto u : g2[v]) {
				if(p == u) continue;
				dfs(u, v);
				dp[v] += dp[u];
			}
		};
		for(auto j : temp) g2[j.first].push_back(j.second);
		dfs(i,-1);
		ans = min(ans, accumulate(dp.begin(), dp.end(), 0LL));
		for(auto &j : g2) j.clear();
	}
	cout << ans;
	return 0;
}

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