oj.uz

Submission #813370

# Submission time Handle Problem Language Result Execution time Memory
813370 2023-08-07T16:26:37 Z SteGG Bosses (BOI16_bosses) C++17
100 / 100
 1118 ms 980 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		// freopen("output.out", "w", stdout);
	}
}

const int inf = 3e18;
const int maxn = 5005;
int n;
vector<int> candidate[maxn];
vector<int> tr[maxn];
bool check[maxn];

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	open();
	cin >> n;
	for(int i = 1; i <= n; i++){
		int k;
		cin >> k;
		for(int j = 1; j <= k; j++){
			int a;
			cin >> a;
			candidate[a].push_back(i);
		}
	}

	int result;
	int last_result = inf;

	auto dfs = [&](auto &&dfs, int u) -> int {
		int sz = 1;
		for(int v : tr[u]){
			sz += dfs(dfs, v);
		}

		result += sz;
		return sz;
	};

	for(int root = 1; root <= n; root++){
		memset(check, false, sizeof(check));
		for(int i = 0; i <= n; i++){
			tr[i].clear();
		}

		queue<pair<int, int>> q;
		q.push({root, 0});
		int cnt = 0;
		while(!q.empty()){
			int u = q.front().first;
			int p = q.front().second;
			q.pop();
			if(check[u]) continue;
			cnt++;
			check[u] = true;
			tr[p].push_back(u);
			for(int v : candidate[u]){
				if(check[v]) continue;
				q.push({v, u});
			}
		}

		if(cnt < n) continue;

		result = 0;

		dfs(dfs, root);
		last_result = min(result, last_result);
	}


	cout << last_result << endl;

	return 0;
}

Compilation message

bosses.cpp: In function 'void open()':
bosses.cpp:8:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 17 ms 880 KB Output is correct
13 Correct 16 ms 960 KB Output is correct
14 Correct 173 ms 828 KB Output is correct
15 Correct 26 ms 724 KB Output is correct
16 Correct 720 ms 980 KB Output is correct
17 Correct 1118 ms 940 KB Output is correct
18 Correct 1047 ms 940 KB Output is correct