oj.uz

Submission #865936

# Submission time Handle Problem Language Result Execution time Memory
865936 2023-10-25T04:31:27 Z maks007 Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -