oj.uz

Submission #383185

# Submission time Handle Problem Language Result Execution time Memory
383185 2021-03-29T06:34:23 Z wind_reaper Bosses (BOI16_bosses) C++17
100 / 100
 923 ms 748 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 5000;
vector<int> g[MXN];
vector<bool> vis;

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int n;
	cin >> n;

	for(int i = 0; i < n; i++){
		int k;
		cin >> k;
		for(int j = 0; j < k; j++){
			int x;
			cin >> x;
			g[x-1].push_back(i);
		}
	}

	int64_t ans = 1e16;
	for(int i = 0; i < n; i++){
		int64_t cost = 0; 
		queue<array<int, 2>> q;
		q.push({i, 1});
		vis.assign(n, 0);
		vis[i] = 1;
		while(!q.empty()){
			int u = q.front()[0], d = q.front()[1];
			q.pop();
			cost += int64_t(d);
			for(int v : g[u]){
				if(!vis[v]){
					vis[v] = 1;
					q.push({v, d+1});
				}
			}
		}
		for(int v = 0; v < n; v++) if(!vis[v]) cost = 1e16;
		ans = min(ans, cost);
	}

	cout << ans << '\n';
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 6 ms 620 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 211 ms 620 KB Output is correct
15 Correct 33 ms 620 KB Output is correct
16 Correct 723 ms 724 KB Output is correct
17 Correct 858 ms 748 KB Output is correct
18 Correct 923 ms 748 KB Output is correct