oj.uz

Submission #76875

# Submission time Handle Problem Language Result Execution time Memory
76875 2018-09-19T01:04:01 Z shoemakerjo Bosses (BOI16_bosses) C++14
100 / 100
 718 ms 1560 KB 
#include <bits/stdc++.h>

using namespace std;

#define maxn 5010
int n;


bool vis[maxn];
vector<vector<int>> ch(maxn);
queue<int> q;
int dep[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int v;
	for (int i = 1; i <= n; i++) {
		int ct;
		cin >> ct;
		for (int j = 0; j < ct; j++) {
			cin >> v;
			ch[v].push_back(i);
		}
		
	}
	int ans = n*n;
	for (int i = 1; i <= n; i++) {
		fill(vis, vis+maxn, false);
		q.push(i);
		dep[i] = 1;
		vis[i] = true;
		int cans = 1;
		while (!q.empty()) {
			v = q.front(); q.pop();
			for (int vv : ch[v]) {
				if (!vis[vv]) {
					dep[vv] = dep[v]+1;
					vis[vv] = true;
					cans += dep[vv];
					q.push(vv);
				}
			}
		}
		bool ok = true;
		for (int j = 1; j <= n; j++) {
			if (!vis[j]) {
				ok = false;
				// cout << "missed!" << endl;
			}
		}
		if (ok) ans = min(ans, cans);
	}
	cout << ans << endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 860 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 3 ms 864 KB Output is correct
8 Correct 2 ms 868 KB Output is correct
9 Correct 3 ms 872 KB Output is correct
10 Correct 3 ms 984 KB Output is correct
11 Correct 3 ms 988 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 3 ms 864 KB Output is correct
8 Correct 2 ms 868 KB Output is correct
9 Correct 3 ms 872 KB Output is correct
10 Correct 3 ms 984 KB Output is correct
11 Correct 3 ms 988 KB Output is correct
12 Correct 7 ms 1120 KB Output is correct
13 Correct 7 ms 1156 KB Output is correct
14 Correct 180 ms 1236 KB Output is correct
15 Correct 33 ms 1260 KB Output is correct
16 Correct 655 ms 1424 KB Output is correct
17 Correct 718 ms 1492 KB Output is correct
18 Correct 700 ms 1560 KB Output is correct