# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
282831 |
2020-08-25T03:55:08 Z |
wutwere |
Bosses (BOI16_bosses) |
C++17 |
|
982 ms |
760 KB |
#include <bits/stdc++.h>
using namespace std;
vector<int> boss[5001];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int k; cin >> k;
for (int j = 0; j < k; j++) {
int b; cin >> b;
boss[b].push_back(i);
}
}
int ans = 1e9;
for (int i = 1; i <= n; i++) {
vector<bool> vis(n + 1);
int nodes = 0, sum = 0;
queue<pair<int, int>> q;
q.push({i, 1});
while (!q.empty()) {
int cur = q.front().first, dep = q.front().second;
q.pop();
if (vis[cur]) continue;
vis[cur] = true;
nodes++;
sum += dep;
for (int b : boss[cur]) {
q.push({b, dep + 1});
}
}
if (nodes == n) {
// cerr << "D " << i << ' ' << sum << '\n';
ans = min(ans, sum);
}
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
30 ms |
640 KB |
Output is correct |
13 |
Correct |
25 ms |
640 KB |
Output is correct |
14 |
Correct |
154 ms |
512 KB |
Output is correct |
15 |
Correct |
4 ms |
512 KB |
Output is correct |
16 |
Correct |
773 ms |
760 KB |
Output is correct |
17 |
Correct |
982 ms |
760 KB |
Output is correct |
18 |
Correct |
982 ms |
736 KB |
Output is correct |