#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
int n;
vector<int> depth;
vector<vector<int>> adj;
int total;
void main_program(){
cin >> n;
adj.resize(n);
for (int i = 0; i < n; i++){
int sz; cin >> sz;
for (int j = 0; j < sz; j++){
int x; cin >> x; x--;
adj[x].push_back(i);
}
}
int res = 1e9;
for (int root = 0; root < n; root++){
depth.assign(n, 0);
total = 1;
queue<int> q; q.push(root); depth[root] = 1;
while (!q.empty()){
int x = q.front(); q.pop();
for (auto k: adj[x]){
if (!depth[k]){
depth[k] = depth[x] + 1;
total += depth[k];
q.push(k);
}
}
}
bool valid = true;
for (int i = 0; i < n; i++){
if (!depth[i]){
valid = false;
break;
}
}
if (!valid) continue;
res = min(res, total);
}
cout << res << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
4 ms |
340 KB |
Output is correct |
13 |
Correct |
3 ms |
340 KB |
Output is correct |
14 |
Correct |
114 ms |
512 KB |
Output is correct |
15 |
Correct |
11 ms |
544 KB |
Output is correct |
16 |
Correct |
472 ms |
576 KB |
Output is correct |
17 |
Correct |
629 ms |
596 KB |
Output is correct |
18 |
Correct |
621 ms |
668 KB |
Output is correct |