#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
vector<int> adjList[n]; //who accepts this person
for (int x = 0; x < n; x++){
int num, temp;
cin >> num;
for (int y = 0; y < num; y++){
cin >> temp;
adjList[temp-1].push_back(x);
}
}
//try every person as root, perform bfs style
long long bestans = LONG_LONG_MAX;
for (int x = 0; x < n; x++){
int depths[n]; //also functions as visited
memset(depths, -1, sizeof(depths));
queue<pair<int, int>> bfs;
depths[x] = 1; //1 for root (a bit unconventional but who cares)
bfs.push(make_pair(x, 1));
while (!bfs.empty()){
int front = bfs.front().first;
int d = bfs.front().second;
bfs.pop();
for (int y : adjList[front]){
if (depths[y] == -1){
//don't touch already used nodes
depths[y] = d+1;
bfs.push(make_pair(y, d+1));
}
}
}
bool failed = false;
long long ans = 0;
for (int y = 0; y < n; y++){
if (depths[y] == -1){ failed = true; break;}
else ans += depths[y];
}
if (!failed) bestans = min(ans, bestans);
}
cout << bestans;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
0 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 |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
0 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 |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 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 |
109 ms |
484 KB |
Output is correct |
15 |
Correct |
4 ms |
468 KB |
Output is correct |
16 |
Correct |
459 ms |
468 KB |
Output is correct |
17 |
Correct |
520 ms |
568 KB |
Output is correct |
18 |
Correct |
490 ms |
596 KB |
Output is correct |