#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> al(5001, vector<int>()), al2;
vector<ll> sub;
void dfs(int i) {
if (al2[i].empty()) return;
for (int v: al2[i]) {
dfs(v);
sub[i]+=sub[v];
}
}
int main() {
int n; cin>>n;
for (int i=1; i<=n; i++) {
int k; cin>>k;
while (k--) {
int v; cin>>v;
al[v].push_back(i);
}
}
ll ans=1e18;
for (int i=1; i<=n; i++) {
sub.assign(n+1,1);
al2.assign(n+1, vector<int>());
vector<int> vis(n+1,0);
queue<int> q;
q.push(i);
vis[i]=1;
while (!q.empty()) {
int u=q.front(); q.pop();
for (int v: al[u]) {
if (vis[v]) continue;
vis[v]=1;
al2[u].push_back(v);
q.push(v);
}
}
dfs(i);
ll s=0;
for (int i=1; i<=n; i++) s+=sub[i];
ans=min(ans,s);
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
552 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
552 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
552 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |