#include <bits/stdc++.h>
using namespace std;
const int mxn = 5005;
int n, k, x, dis[mxn], sal[mxn], sum, ans = 2e9;
vector<int> adj[mxn], adj2[mxn];
queue<int> q;
void bfs(int st) {
q.push(st);
dis[st] = 0;
while (!q.empty()) {
int p = q.front();
q.pop();
for (int i : adj[p]) {
if (dis[i] != -1) continue;
q.push(i);
dis[i] = dis[p] + 1;
adj2[p].push_back(i);
}
}
}
void dfs(int x) {
sal[x] = 1;
for (int i : adj2[x]) {
dfs(i);
sal[x] += sal[i];
}
sum += sal[x];
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> k;
while (k--) {
cin >> x;
adj[x].push_back(i);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[j] = -1;
adj2[j].clear();
}
bfs(i);
for (int j = 1; j <= n; j++) {
if (dis[j] == -1) goto end;
}
sum = 0;
dfs(i);
ans = min(ans, sum);
end:;
}
cout << ans << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
564 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
564 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
564 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
564 KB |
Output is correct |
12 |
Correct |
5 ms |
724 KB |
Output is correct |
13 |
Correct |
4 ms |
704 KB |
Output is correct |
14 |
Correct |
187 ms |
768 KB |
Output is correct |
15 |
Correct |
24 ms |
852 KB |
Output is correct |
16 |
Correct |
642 ms |
896 KB |
Output is correct |
17 |
Correct |
1280 ms |
964 KB |
Output is correct |
18 |
Correct |
1266 ms |
980 KB |
Output is correct |