# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
857759 |
2023-10-06T21:45:32 Z |
qrno |
Bosses (BOI16_bosses) |
C++17 |
|
548 ms |
860 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) begin(v), end(v)
int N;
vector<vector<int>> G;
int bfs(int v) {
vector<int> val(N, -1);
queue<pair<int, int>> Q;
val[v] = 1;
Q.push({v, val[v]});
while (!Q.empty()) {
auto [v, x] = Q.front(); Q.pop();
for (auto u : G[v]) {
if (val[u] == -1) {
val[u] = x+1;
Q.push({u, val[u]});
}
}
}
if (*min_element(all(val)) == -1) return -1;
return accumulate(all(val), 0LL);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N;
G.resize(N);
for (int i = 0; i < N; i++) {
int K; cin >> K;
while (K--) {
int u; cin >> u; u--;
G[u].push_back(i);
}
}
int best = -1;
for (int i = 0; i < N; i++) {
int sum = bfs(i);
if (sum == -1) continue;
if (best == -1 || best > sum)
best = sum;
}
cout << best << endl;
}
# |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
448 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
448 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
3 ms |
564 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
142 ms |
728 KB |
Output is correct |
15 |
Correct |
27 ms |
600 KB |
Output is correct |
16 |
Correct |
537 ms |
860 KB |
Output is correct |
17 |
Correct |
548 ms |
820 KB |
Output is correct |
18 |
Correct |
526 ms |
816 KB |
Output is correct |