Submission #865936

#	Time	Username	Problem	Language	Result	Execution time	Memory
865936		maks007	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	348 KiB

bosses

#include "bits/stdc++.h"

using namespace std;

#define int long long

signed main () {
	int n, mn = LLONG_MAX;
	cin >> n;
	vector <int> g[n];
	vector <pair <int,int>> edge;
	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(accumulate(dist.begin(), dist.end(), 0LL) < mn) {
			mn = accumulate(dist.begin(), dist.end(), 0LL);
			edge = temp;
		}
	}
	for(auto &i : g) i.clear();
	for(auto i : edge) g[i.first].push_back(i.second);
	vector <int> dp(n, 0);
	function <void(int,int)> dfs=[&](int v, int p) {
		dp[v] ++;
		for(auto u : g[v]) {
			if(u == p) continue;
			dfs(u, v);
			dp[v] += dp[u];
		}
	};
	int root = edge[0].first;
	dfs(root, -1);
	cout << accumulate(dp.begin(), dp.end(), 0LL);
	return 0;
}

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