#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5005;
int n, k, x, seen=0;
ll ans = 1e18, dp[maxn+5];
vector<int> graph[maxn+5], tree[maxn+5], vis(maxn+5);
queue<int> q;
ll dfs(int u) {
dp[u] = 1;
for(int &v : tree[u]) dp[u] += dfs(v);
return dp[u];
}
int32_t main() {
cin >> n;
for(int i=1; i<=n; i++) {
cin >> k;
for(int j=0; j<k; j++) {
cin >> x;
graph[x].push_back(i);
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) vis[j] = dp[j] = 0, tree[j].clear();
q.push(i); vis[i] = 1; seen = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
seen++;
for(int &v : graph[u]) {
if(vis[v]) continue;
vis[v] = 1;
tree[u].push_back(v);
q.push(v);
}
}
if(seen < n) continue;
dfs(i);
ll res = 0;
for(int j=1; j<=n; j++) res += dp[j];
ans = min(ans, res);
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
696 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
696 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
6 ms |
860 KB |
Output is correct |
13 |
Correct |
4 ms |
860 KB |
Output is correct |
14 |
Correct |
143 ms |
1024 KB |
Output is correct |
15 |
Correct |
27 ms |
860 KB |
Output is correct |
16 |
Correct |
539 ms |
1060 KB |
Output is correct |
17 |
Correct |
888 ms |
1088 KB |
Output is correct |
18 |
Correct |
871 ms |
1088 KB |
Output is correct |