oj.uz

Submission #865937

# Submission time Handle Problem Language Result Execution time Memory
865937 2023-10-25T04:45:02 Z maks007 Bosses (BOI16_bosses) C++14
0 / 100
 0 ms 348 KB 
#include "bits/stdc++.h"

using namespace std;

#define int long long

signed main () {
	int n, ans = LLONG_MAX;
	cin >> n;
	vector <int> g[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);
				}
			}
		}
		vector <int> g2[n];
		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));
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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